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.


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)$


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.

  • $\begingroup$ Isnt $\varphi(pq) = \varphi(p) * \varphi(q)$ only when $gcd(p,q)=1$. $\endgroup$ – maverick Oct 11 '16 at 16:33
  • $\begingroup$ @maverick Yes, $\gcd(p,q)=1$. $q$ contains the primes not shared with $x$, and $p$ the rest of the prime decomposition of $m$. Sorry if it was unclear $\endgroup$ – Evariste Oct 11 '16 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.