Saturday, March 01, 2008

(a + b)p ≡ ap + bp (mod p)

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 :

David said...

I was a little bit confused by "p!/(m!)(p-m)! = p*([(p-1)*...*p-m+1]/[m!])". how did you get this?

Larry Freeman said...

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.