Fermat's little theorem states that

if $n$ is a prime number then $a^n \equiv a \pmod n$.

Euler's theorem and Carmichael's theorem relax it from "if $n$ is a prime number" to

if $a$ and $n$ are coprime integers then $a^m \equiv a \pmod n$.

, where $m=\phi(n)+1$ for Euler's theorem and $m=\lambda(n)+1$ for Carmichael's theorem.

That theorems are pretty amazing and simplify modular calculations a lot.

But what if $a$ and $n$ aren't coprimes? Are there some generalisations to previous theorems for arbitrary $a$ and $n$, or for $a$ and $n$ with even more relaxed requirements?

  • 1
    $\begingroup$ That should be $m = \phi(n)+1$ and $\lambda(n)+1$. $\endgroup$ – Robert Israel Oct 13 '16 at 6:50

If, for example, prime $p$ divides both $a$ and $n$ but $p^2$ divides $n$ and does not divide $a$, then $a^m \not\equiv a\; (\text{mod}\; n)$ for any $m > 1$.

On the other hand, if $n$ is squarefree then for any $a$, $a^{\lambda(n)+1} \equiv a \; (\text{mod}\; n)$.


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.