Find $(a^a)^{a^a}$ mod $n$

Question

We need to find $(a^a)^{a^a}$ % $n$, for $1 \le a,n \le1000$ wher $gcd(a,n) \ne 1$.
% denotes modulo operation.
I could have used Euler's Theorem but its not true that $a,n$ are co-prime.

Answer 1

Theorem : we can use Euler's theorem for $x^y \pmod m$ even when $gcd(x,m)\neq1$ as long as the residue used in the exponentiation is equal or bigger than the highest power of the prime powers shared by $x$ and $m$

Proof : Let's write $m=pq$ such that $\gcd(x,q)=1$ and $n|p \rightarrow n|x$

(so $\gcd(p,q)=1$)

Euler's theorem yields $x^{\varphi(q)} \equiv 1 \pmod q$

Since $\varphi(m)=\varphi(pq)=\varphi(p)\varphi(q),$ $x^{\varphi(m)}\equiv1 \pmod q$

Besides, assume $k\geq max_{p'|p} \frac{v_{p'}(m)}{v_{p'}(x)}$ where $v_{p'}$ denotes $p'$-adic valuation.

Since $p|x^k, m=pq|(x^{k+\varphi(m)}-x^k)=x^k(x^{\varphi(m)}-1)$

Q.E.D

In other words, user Euler's but stop above the highest shared power.

E.g. to solve $12^x \pmod {100}$, since $100=2^\color{red}{2}\times5^2$ and $12=3\times2^\color{red}{2}$, the highest shared power is $2$. So compute $x \pmod {\varphi(100)}$ until the value is the smallest value greater or equal to $2$. Then do the rest of the calculation by hand.