# Proof congruence

• November 18th 2007, 11:35 PM
AgentNXP
Proof congruence
Show that if p is a prime, then (a + b)^p ≡ a^p + b^p (mod p)
(Hint: prove and use that p choose k is a multiple of p for every k ∈ {1, . . . , p − 1}). Then expand (a + b)^p via the binomial theorem).
Using the previous formula, prove Fermat’s little Theorem (in its equivalent form, a^p ≡ a (mod p)) by induction on a.

Any help appreciated!
• November 19th 2007, 06:12 AM
Plato
Consider the fact that $\left( {\begin{array}{c} p \\ k \\ \end{array}} \right) = \frac{{p!}}{{k!\left( {p - k} \right)!}}\;,\;k \in \left\{ {1,2, \cdots ,p - 1} \right\}$.
Then note that because p is prime neither k! nor (p-k)! is a factor of p.
So p is a factor of $\left( {\begin{array}{c} p \\ k \\ \end{array}} \right),\;k \in \left\{ {1,2, \cdots ,p - 1} \right\}$.

$\left( {a + b} \right)^p = \sum\limits_{k = 0}^p {\left( {\begin{array}{c}
p \\ k \\ \end{array}} \right)a^{p - k} b^k } = a^p + \sum\limits_{k = 1}^{p - 1} {\left( {\begin{array}{c} p \\ k \\ \end{array}} \right)a^{p - k} b^k } + b^P$
.

Can you see how to complete the argument?
• November 19th 2007, 09:00 AM
ThePerfectHacker
You can use {p\choose k} to save time.
• November 19th 2007, 09:04 AM
Krizalid
Of course

$\binom pk$ made it with \binom pk.

(The space is necessary, but when using numbers, for example, \binom23 there's no problem.)
• November 19th 2007, 09:13 AM
Jhevon
Quote:

Originally Posted by ThePerfectHacker
You can use {p\choose k} to save time.

this is what i always use

Quote:

Originally Posted by Krizalid
Of course

$\binom pk$ made it \binom pk.

(The space is necessary, but when using numbers, for example, \binom23 there's no problem.)

this is nice!