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

**Geoffrey** · November 12th 2006, 03:30 PM

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?

**ThePerfectHacker** · November 12th 2006, 03:41 PM

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.

**Geoffrey** · November 12th 2006, 03:47 PM

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

**ThePerfectHacker** · November 12th 2006, 04:04 PM

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)

**Geoffrey** · November 12th 2006, 05:00 PM

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!

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Prove that [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab)

[SOLVED] Every prime > 3 is congruent to \pm 1 mod 6

prove a congruent angle with a bisector

Prove: If ab congruent to 1 (mod m), then o(a) equals o(b).

Search Tags