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...

  • 1
    $\begingroup$ You may be interested in Carmichael numbers. $\endgroup$ – lhf Oct 25 '13 at 3:08
  • $\begingroup$ @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) $\endgroup$ – Tobias Kienzler Oct 25 '13 at 8:03
  • $\begingroup$ @lhf Thanks again for your comment, it lead me to Knödel numbers and an actual answer (assuming it is correct...) $\endgroup$ – 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

| cite | improve this answer | |

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.