Has anyone seen the movie "The Kingdom of Heaven"? Besides the thing that the movie is very well made, the character of Salahuddin acted very well in that movie. I liked the character so much that I got tempted to keep the name of this blog after it.

Friday, August 20, 2010

Fermat's theorem about prime numbers

I could also prove the fermat's theorem about prime numbers,

(2^p - 1) == 1 (mod p) for any prime number. The proof uses binomial expansion.

sum of all nCr, r from 0 to n is 2^n. If we keep a prime number p for n,

pCr, r from 0 to p is 2^p.
In these co-efficients, except pC0, and pCp, everything else must have p as a factor, since, p is a prime.

So, finally, pC0 + pCp + pK = 2^p.
pK + 1 = 2^p - 1.

So, (2^p - 1) == 1 (mod p).

I was pleasantly surprised about this, although.
(This is called Fermat's little theorem)

The statement is more generic. If p is a prime, for any integer a, a^p == a (mod p).
This can be proved using induction, on a.

1^p == 1 (mod p) trivial, we have also seen 2^p == 2 (mod p) incidentally.
Also assume that n^p == n (mod p).
(n + 1)^p = Sum from 0 to p (pCr * n^r)

All terms except pC0 and pCp have p as the factor. So,

pC0 + pCp * n^p + pK = (n + 1)^p
n^p == n (mod p)
So,
pK + (n + 1) = (n + 1) ^p
So, (n + 1) ^p == (n + 1) mod p

No comments:

Post a Comment