# Proof of Fermat's little theorem using congruence modulo $p$

I have managed to show that $(a + b)^p \equiv a^p + b^p \pmod p$, $a$ and $b$ being any integer and $p$ any prime.

How can I prove from this that $a^p \equiv a \pmod p$?

-
This is Fermat’s so-called little theorem; you’ll find several proofs here. The one using the binomial theorem is probably the one that you want: use induction, taking $b=1$. –  Brian M. Scott May 27 '12 at 7:20
I've edited the title of your post to match better your question. Recommendation form here: How can I ask a good question? Make your title as descriptive as possible. –  Martin Sleziak May 27 '12 at 7:26
@Martin: The trouble with title edits such as this is that it can make people think (if they don't look too closely) that the OP knew the name of the theorem and was just lazy about googling for a proof, whereas if you don't know the name, it's pretty hard to google. –  Tara B Feb 19 '13 at 11:32
@TaraB You are of course right, but I don't think that is such a big issue. –  Martin Sleziak Feb 19 '13 at 12:29

Converting from a comment:

This result is usually known as Fermat’s little theorem; you’ll find several proofs here. The one using the binomial theorem appears to be exactly what you want. In case you’d rather work on it a bit yourself with the benefit of a hint, I’ll just say that the key idea is to prove it by induction on $a$, substituting $b=1$ into the result that you’ve already proved.

-

Alternatively, using the euclidean algorithm, you can show that gcd(a,b) = as + bt for some $s$ and $t$. Since every positive integer $1 \leq a \leq p - 1$ where $p$ is prime has gcd(a,p) = 1, one has that $as + bp = 1$ so $as \equiv 1 \mod p$. So the $\{1, ..., p - 1\}$ forms a group under multiplication. By basic group theory, every element raised to its order is the identity. So $a^{p - 1} = 1 \text{mod} p$. So $a^p = a \text{ mod }p$.

This idea of raising elements to the order of the group or a multiple of the order of the group is very useful for arguments in number theory.

-

Once you know that $(a + b)^p \equiv a^p + b^p \pmod p$, you have essentially shown that the map $F:x\mapsto x^p$ is an endomorphism of the ring $\mathbf Z/p\mathbf Z$ (the proof in fact shows that this is true in any commutativie ring of characteristic $p$, and the endomorphism is called the Frobenius endomorphism), because $(xy)^p=x^py^p$ and $1^p=1$ are obvious.

You can now conclude that this endomorphism $F$ is the identity $\mathbf 1$ (in other words $a^p=a$ for all $a\in\mathbf Z/p\mathbf Z$) as follows. Like for any (unitary) ring, there is a unique (unitary) ring morphism $\pi:\mathbf Z\to\mathbf Z/p\mathbf Z$ (this general fact is what justifies using an integer to uniquely designate an element in any unitary ring), which in this case is of course the canonical projection, and hence surjective. Now by uniqueness $\pi=F\circ\pi=\mathbf 1\circ \pi$, and by surjectivity $F=\mathbf 1$.

-