Thread: 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!

Consider the fact that .
Then note that because p is prime neither k! nor (p-k)! is a factor of p.
So p is a factor of .

.

Can you see how to complete the argument?

You can use {p\choose k} to save time.

Of course

made it with \binom pk.

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

Originally Posted by ThePerfectHacker

You can use {p\choose k} to save time.

this is what i always use

Originally Posted by Krizalid

Of course

made it \binom pk.

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

this is nice!