# Prove: For ever prime p and integer a, a^p is congruent to a (mod p)

• Nov 12th 2006, 03:30 PM
Geoffrey
Prove: For ever prime p and integer a, a^p is congruent to a (mod p)
Well, I have noticed that for every integer a in a prime mod p, a^(p - 1) is congruent to 1 (mod p). I don't know why this is though, and if I had a proof for it, I could use the multiplicative property of congruency to show a^p is congruent to a (mod p). What should I do?
• Nov 12th 2006, 03:41 PM
ThePerfectHacker
Quote:

Originally Posted by Geoffrey
Well, I have noticed that for every integer a in a prime mod p, a^(p - 1) is congruent to 1 (mod p). I don't know why this is though, and if I had a proof for it, I could use the multiplicative property of congruency to show a^p is congruent to a (mod p). What should I do?

The name of this result was discovered by my favorite mathemation, Fermat.
"Fermat's Little Theorem"

I have 3 proofs.

1 uses congruences and Pigeonhole Principle.

1 uses Lagrange's Theorem from Group Theory.

1 is my own proof using induction and alchemy.
• Nov 12th 2006, 03:47 PM
Geoffrey
May I see the first one that uses congruences and the pigeonhole principle? I really am unsure about how to go about that one.
• Nov 12th 2006, 04:04 PM
ThePerfectHacker
Quote:

Originally Posted by Geoffrey
May I see the first one that uses congruences and the pigeonhole principle? I really am unsure about how to go about that one.

Let $p$ prime and $a$ an integer such as $\gcd(a,p)=1$.
Consider the integers,
$1a,2a,3a,...,(p-1)a$
Now two are congruent to each other for that will yield,
$ra\equiv ka (\mbox{mod }p)$
Since, $\gcd(a,p)=1$ division yields,
$r\equiv k (\mbox{mod }p)$
Which is impossible for $r\not = k$ and $1 \leq r,k\leq p-1$ so they have different remainders.

Thus,
$1a,2a,3a,....,(p-1)a$ form "a complete set of residues".
What does that mean?
Well it means,
$1a\equiv r_1$
$2a\equiv r_2$
$3a\equiv r_3$
...
$(p-1)a\equiv r_{p-1}$
Where $r_1,r_2,...,r_{p-1}$ are the remainders they leave.

But by Dirichelt's Pigeonhole Principle they are the integers $1,2,3,...,p-1$ (not necessarily in that order).

Multiply these congruences,
$\prod_{k=1}^{p-1} k a\equiv \prod_{k=1}^{p-1}r_k (\mbox{mod }p)$

But, $\prod_{k=1}^{p-1}r_k=(p-1)!$ (as explained before).

Thus,
$(p-1)! a^{p-1}\equiv (p-1)! (\mbox{mod }p)$
Also, $\gcd((p-1)!,p)=1$
Division yields,
$a^{p-1}\equiv 1(\mbox{mod }p)$
Q.E.D.
(Applause)
• Nov 12th 2006, 05:00 PM
Geoffrey
Okay, I finally got it. We have very similar proofs, but I rely more on properties I've previously discovered about modulus on other homework sets. Thank you so much for your help! :)