# Proof for Fermat's Little Theorem

The proof was given as:

1. Let $p\in\mathbb{N}^{+}$
2. Let $a\in\mathbb{N}$
3. Let $p$ be prime
4. We know that $p\,\vert\,a^p-a$ by proposition of Chapter 1
5. Therefore $a^p-a\equiv 0\pmod p$ by Definition 8.4.1
6. Therefore $a^p\equiv a\pmod p$ by Proposition 8.4.7

Q.E.D.

But how do I get from 4 to 5 and 5 to 6?

Is 4 to 5 trying to say, since $p$ divides $(a^p - a)$ then the remainder is always 0? Then 5 - 6, how do I just move the $a$ over?

1 (original question)

-
Step 4. is critical. If you understand that, you know the essence. Step 5. and 6. are trivial by definition of $\equiv$, and goes exactly as you wrote at the end. – Berci Nov 30 '12 at 10:31

The step from 4 to 5 is just the definition of congruence. By definition $a\equiv b\pmod m$ means that $m\mid a-b$, so if you know from step 4 that $p\mid a^p-a$, then you know that $p\mid(a^p-a)-0$ and hence by definition that $a^p-a\equiv 0\pmod p$. In fact step 5 is unnecessary, since you can go directly from 4 to 6: if you know that $p\mid a^p-a$, then you know that $a^p\equiv a\pmod p$ by the definition of congruence.

However, you getting from 5 to 6 is also completely straightforward. More generally,

$$a\equiv b\pmod m\quad\text{iff}\quad a-b\equiv 0\pmod m\;.$$

By definition $a\equiv b\pmod m$ means that $m\mid a-b$, but that’s certainly true if and only if $m\mid(a-b)-0$, which means exactly that $a-b\equiv 0\pmod m$.

-