Lemma 1:
if p is prime, then:
(a + b)p ≡ ap + bp (mod p)
Proof:
(1) Using the Binomial Theorem (see Theorem here), we know that:
(2) Now, since p is a prime, it is clear that for each term p!/(m!)(p-m)!, p is not divisible by any term ≤ m or by any term ≤ p-m so that we have:
p!/(m!)(p-m)! = p*([(p-1)*...*p-m+1]/[m!])
(3) This shows that each of these terms is divisible by p and therefore:
[p!/(m!)(p-m)!]ap-mbm ≡ 0 (mod p)
(4) So that there exists an integer n such that:
(a + b)p = ap + np + bp
(5) Since ap + nb + bp ≡ ap + bp (mod p), it follows that:
(a + b)p ≡ ap + bp (mod p)
QED
2 comments :
I was a little bit confused by "p!/(m!)(p-m)! = p*([(p-1)*...*p-m+1]/[m!])". how did you get this?
Hi David,
That comes from the definition of a factorial.
p! = p*(p-1)*...*2*1
If we assume that m is less than p, we have:
(p-m)! = (p-m)*(p-m-1)*...*2*1
So that:
p!/(p-m)! = p*(p-1)*...*(p-m+1)
I hope that helps.
Post a Comment