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
(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
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment