Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
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

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.