Related to Fermat's Little Theorem

Question

How obvious it is to have $$a^p\equiv a \pmod p$$ where $a$ is an integer and $p$ is a prime.

Can you feel it true? May you please explain it to me in very simple words that how $a^p$ and $a$ leaves the same remainder when divided by $p$.

Answer 1

It's not at all obvious. Quite likely, Fermat observed the fact for all “small” primes and so tried to see whether it holds for every prime.

It's not the same as other proofs with “infinite descent”, because it's not possible to reduce to a smaller prime, or, at least, I can't see how it could be done.

By the binomial theorem, $$ (b+1)^p=\sum_{k=0}^p \binom{p}{k}b^k $$ Since $p\mid\binom{p}{k}$ for $0<k<p$, we can see that $$ p\mid\bigl((b+1)^p-(b+1)\bigr) $$ Set $b+1=a$ and you're done.

The binomial theorem had been known for several decades when Fermat did his work. Note however that there is no known proof by Fermat himself; the first proof was published by Euler in 1749.

Answer 2

When a and p are coprime, note that $a, 2a, 3a,....... (p-1)a$ all leave different remainders when divided by $p\in [1, p-1]$. Multiply all the congruences and eliminate $(p-1)!$ from the resulting congruence as gcd$[(p-1)!, p] = 1$. You get the desired result by multiplying $a$ on both sides afterward