# What is $a^n\bmod n$ for composite $n$?

While Fermat's little theorem states that $$a^p\equiv a\pmod p$$ for any prime number $p$, which may be considered a consequence of Euler's theorem $$a^{\phi(n)}\equiv 1\pmod n\tag{e}\label{e}$$ (for $n\nmid a$) since $\phi(p)=p-1$ for $p$ prime, I was wondering

whether there is any similar statement one can make about $a^n\bmod n$ when $n$ is not a prime number.

As a simplest example, take $n=p^2$ such that $\phi(n)=p(p-1)$, so $$a^{p^2}\equiv a^{\phi(p^2)+p}\stackrel{\eqref{e}}\equiv a^p\pmod{p^2}$$ or for $n=pq$ with $p\neq q$ (i.e. $\phi(n)=(p-1)(q-1)$) $$a^{pq}\equiv a^{\phi(pq)+p+q-1}\stackrel{\eqref{e}}\equiv a^{p+q-1}\pmod{pq}$$ (assuming $n\nmid a$), but these are rather "boring" identities...

I also wonder whether the exponential cycle $$a^{\lambda(n)+k}\equiv a^k\pmod n$$ plays a role here...

• You may be interested in Carmichael numbers. – lhf Oct 25 '13 at 3:08
• @lhf Interesting numbers, thanks! So my question now boils down to "Appart from Carmichael numbers $b$, where $b^n\equiv b\pmod n$..." ;) Hm, also interesting then: Knödel numbers (though at first glance Wikipedia seems to contradict the Mathworld entry) – Tobias Kienzler Oct 25 '13 at 8:03
• @lhf Thanks again for your comment, it lead me to Knödel numbers and an actual answer (assuming it is correct...) – Tobias Kienzler Oct 31 '13 at 8:19

Since $\lambda(n)+v_\max(n)\leqslant n$, the $k\geqslant v_\max(n)$ in the exponential cycle $$a^{\lambda(n)+k}\equiv a^k\pmod n$$ can be chosen as $k=n-\lambda(n)\geqslant v_\max(n)$ to obtain $$a^n \equiv a^{n-\lambda(n)} \pmod n$$ As special cases, observe that for prime numbers (and Fermat pseudoprimes), where $\lambda(n)=\phi(n)=n-1$, this yields Fermat's little theorem; while the two examples from the question are also included.
Note how this yields $n\in K_{n-\lambda(n)}$, i.e. each (composite) $n$ is a Knödel number