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
    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
up vote 0 down vote accepted

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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