# Prove that $a^{n} \bmod n$ congruent to $a^{n - \phi(n)} \bmod n$

I'm looking to prove that these two are congruent to one another mod n, For all positive integers a and all positive integers n.

$$a^{n} = a^{n - \phi(n)} \bmod n$$

The problem is I don't know where to start, I don't have much practice with modular arithmetic proofs so this has posed to be quite a challenge for me.

• I believe you want $\gcd(a,n) = 1$. Then this follows from Euler's totient theorem. Commented Mar 19, 2017 at 19:26
• @EthanAlwaise The challange is to show it in the case that $a$ and $n$ are not coprime. Commented Mar 19, 2017 at 20:11

If $a$ and $n$ are coprime, we have $$a^{\phi(n)}\equiv 1\mod n$$

(Euler's theorem)

If $a$ and $n$ are not coprime, we need the Carmichael function (https://en.wikipedia.org/wiki/Carmichael_function)

Since $\lambda(n)|\phi(n)$, we only need to show that $n-\phi(n)$ is greater than or equal to the largest exponent in the prime factorization of $n$. Suppose , the largest prime power dividing $n$ is $p^k$. Then, we have $\phi(n)<=\frac{p-1}{p}\cdot n$ , hence $n-\phi(n)\ge \frac{n}{p}\ge p^{k-1}>k$ , completing the proof.

• Your counterexample isn't a counterexample to the congruence given by the OP (which I believe does hold in general). Commented Mar 19, 2017 at 19:44

Outline:

If true for $a_1$ and $a_2$ then it is true for $a=a_1a_2$.

So we only have to prove it for primes $a$ and $a=\pm 1$. The case $a=\pm 1$ is easy.

If $a$ is prime and $a$ does not divide $n$, the $a^{\phi(n)}\equiv 1\pmod{n}$ and we are done.

If $a$ is prime and divides $n$, write $n=a^{k}n_1$ where $a$ does not divide $n_1$. Then:

$$n-\phi(n)=n_1a^k - a^{k-1}(a-1)\phi(n_1) = a^k(n_1-\phi(n_1)) +a^{k-1}\phi(n_1)$$

So $$a^{n-\phi(n)}=(a^{n_1-\phi(n_1)})^{a^k}a^{a^{k-1}\phi(n_1)}$$

Use this to show that:

$$a^{n-\phi(n)}\equiv 0\equiv a^{n}\pmod{a^k}$$

and:

$$a^{n-\phi(n)}\equiv a^n\pmod{n_1}$$