I know that if $p$ prime and $p\nmid a$, then $a^{p-1}\equiv 1\pmod p$ and I know also that $a^{p}\equiv a \pmod p$ using the fact $a\equiv a \pmod p$ and multiplying the members.

What I couldn't understand is why in the Fermat little theorem we have $a^{p}\equiv a \pmod p$ for all integer $a$.

  • 2
    $\begingroup$ I don't understand your question properly. $\endgroup$
    – rah4927
    May 1 '14 at 5:40
  • 2
    $\begingroup$ If $p$ divides $a$ then both $a^p$ and $a$ are congruent to $0$. $\endgroup$ May 1 '14 at 5:42
  • $\begingroup$ @AndréNicolas of course!!! thanks $\endgroup$
    – user42912
    May 1 '14 at 5:43
  • $\begingroup$ You already know the result for coprime p and a. If $p|a$ , $a^p\equiv 0\pmod p$ and since $0\equiv a\pmod p$, and the claim follows. $\endgroup$
    – rah4927
    May 1 '14 at 5:44
  • $\begingroup$ @user42912: You are welcome. Sometimes "too easy" can be hard to see, we look for something fancy. $\endgroup$ May 1 '14 at 5:46

If $p$ divides $a$ then both $a^p$ and $a$ are congruent to $0$, so $a^p\equiv a\pmod{p}$ holds trivially.

Remark: From $a^p\equiv a\pmod{p}$, we can conversely derive the more common form of Fermat's Theorem. For if $a^p\equiv a\pmod p$, then $p$ divides $a(a^{p-1}-1)$. So if $p$ does not divide $a$, then $p$ divides $a^{p-1}-1$.


Either $p$ divides $a$ or $p\nmid a$

As $p$ is prime $p\nmid a\implies (a,p)=1$

As $\displaystyle a^p-a=a(a^{p-1}-1)$

This will be divisible by $p$ if $p|a$

otherwise it will also be divisible by $p$ as $p|(a^{p-1}-1)$ by Fermat little theorem


Following the comments of André Nicholas:

If $p\mid a$, then $a\equiv 0 \pmod p$, then multiplying $p$ times both sides we have $a^p\equiv 0 \pmod p$. Thus we have $a\equiv 0 \pmod p$ and $0\equiv a^p\pmod p$ by symmetry, then finally by transitivity:

$$a\equiv a^p \pmod p$$


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.