It's been around 9 months since my first and last post. (Just checked the date, exactly 9 months). I had said that I'd try to be regular, but if someone really trusted me on that, it's their fault.
The statement of the theorem is pretty simple like most of the theorems by Fermat.
For a prime number p and a whole number n, n^p - n is divisible by p.
So, as I said that I'd write about interesting stuff I come across, this post is about an interesting theorem I recently came across, called Fermat's Little Theorem.
The statement of the theorem is pretty simple like most of the theorems by Fermat.
For a prime number p and a whole number n, n^p - n is divisible by p.
And like most of his theorems, Fermat didn't leave any proof.
The theorem was first proved by Leibniz around 1683, but he never published it. The first published proof came from Euler. Both Leibniz and Euler gave essentially same proof. I decided to give it a try on my own before looking at their proof.
First thing that I did was to factorize the expression.
n^p - n = n (n ^ (p - 1) - 1)
So, the case when n is divisible by p becomes trivial. Now, the goal was to prove that
n ^ (p - 1) - 1 is divisible by p, if n is not divisible by p.
The idea that came to my mind was induction.
But before that, I thought of trying to do some arbitrary geometric series stuff, but made a stupid mistake in that and ended up wasting time because I found some impossible results. I tried to prove it using induction and binomial theorem, but no success. Even Prateek Agrawal tried something similar, but that didn't work.
After wondering for some time, I finally decided to try induction on original problem and the following proof came out.
To Prove : For a prime number p and a whole number n, n^p - n is divisible by p.
Base step : The proof for n = 0, and n = 1 is trivial.
Induction Step : Assume statement is true for n and try to prove for n+1.
So we assume that n^p - n is divisible by p
i.e. n^p - n = k*p, k is a whole number.
Now goal is to prove that (n+1) ^ p - (n + 1) is divisible by p.
Proof : Expand (n + 1) ^ p using binomial theorem
We'll get
(n^p - n) + p*n^(p - 1) + p*(p - 1)*n^(p - 2)/2 + ..... + p*n
n^p - n in this step is divisible by p(as assumed), for the remaining part we can write it as
p*(n^(p - 1) + (p - 1)*n^(p - 2)/2 + .... + n)
Now if we can write it as k*p. All we need to show is that k is an integer. Here we can use the fact that p is prime, and claim that k is integer. And woah, our proof is done. That wasn't too difficult.
If you want a more awesome proof, you can check the proof by Leibniz here.
There are a lot of other interesting things related to this theorem like Fermat Primality Test which is based on converse of this theorem (which is not true), so it's a probable primaliaty test. The biggest problem for this test comes from Carmichael Numbers. These are composite numbers and for all n co-prime to them, n^p - n is divisible by p, where p is the Carmiachael Number.
Also encryption program PGP used Fermat Primality test because the probability of generating a Carmiachael number is pretty small.
I guess that's it for today. Will try to post something else soon. If someone finds some flaw in the proof, please let me know.
P.S. :- Thanx to Prateek Agrawal for his help with the proof.
The theorem was first proved by Leibniz around 1683, but he never published it. The first published proof came from Euler. Both Leibniz and Euler gave essentially same proof. I decided to give it a try on my own before looking at their proof.
First thing that I did was to factorize the expression.
n^p - n = n (n ^ (p - 1) - 1)
So, the case when n is divisible by p becomes trivial. Now, the goal was to prove that
n ^ (p - 1) - 1 is divisible by p, if n is not divisible by p.
The idea that came to my mind was induction.
But before that, I thought of trying to do some arbitrary geometric series stuff, but made a stupid mistake in that and ended up wasting time because I found some impossible results. I tried to prove it using induction and binomial theorem, but no success. Even Prateek Agrawal tried something similar, but that didn't work.
After wondering for some time, I finally decided to try induction on original problem and the following proof came out.
To Prove : For a prime number p and a whole number n, n^p - n is divisible by p.
Base step : The proof for n = 0, and n = 1 is trivial.
Induction Step : Assume statement is true for n and try to prove for n+1.
So we assume that n^p - n is divisible by p
i.e. n^p - n = k*p, k is a whole number.
Now goal is to prove that (n+1) ^ p - (n + 1) is divisible by p.
Proof : Expand (n + 1) ^ p using binomial theorem
We'll get
(n^p - n) + p*n^(p - 1) + p*(p - 1)*n^(p - 2)/2 + ..... + p*n
n^p - n in this step is divisible by p(as assumed), for the remaining part we can write it as
p*(n^(p - 1) + (p - 1)*n^(p - 2)/2 + .... + n)
Now if we can write it as k*p. All we need to show is that k is an integer. Here we can use the fact that p is prime, and claim that k is integer. And woah, our proof is done. That wasn't too difficult.
If you want a more awesome proof, you can check the proof by Leibniz here.
There are a lot of other interesting things related to this theorem like Fermat Primality Test which is based on converse of this theorem (which is not true), so it's a probable primaliaty test. The biggest problem for this test comes from Carmichael Numbers. These are composite numbers and for all n co-prime to them, n^p - n is divisible by p, where p is the Carmiachael Number.
Also encryption program PGP used Fermat Primality test because the probability of generating a Carmiachael number is pretty small.
I guess that's it for today. Will try to post something else soon. If someone finds some flaw in the proof, please let me know.
P.S. :- Thanx to Prateek Agrawal for his help with the proof.
