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.
 A: 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.
A: 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}$$
