Fermat's Little Theorem

           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.

           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.

Welcome to the world of randomness

So here I am. After thinking for a long time about starting a blog, I am finally here.
So, what took me so long ??
       Well, whenever I thought about starting a blog, the first question that always came to my mind was what to write about . As I'm too lazy (maybe not as lazy as my friend Prateek) to think about some topic and notorious for delaying everything as much as I can (if you don't believe me, ask my father ) , so I just dropped the idea every time.

     So what made me finally start this blog, and what am I going to write about ?
We'll come to the more difficult question later .

     First of all I would like to give credit for this blog to 3, no 4 persons .
First of them is Ajeet, my colleague cum mentor at my intern , who advised me to start writing about anything that comes to my mind. Now as always I started searching my mind for the topics, and as always I was about to give up. But then comes my friend Saheel with his new blog which you can follow here. I liked his idea, got motivated. But needed a final push, and then entry of  my friend Sujit , like a hindi film hero.
     After he encouraged me to start my blog, I had no choice but to start something, because I knew (and you will also know if you know Sujit ) that he would nag me to death if I don't start writing.
So these are the people without whom this blog would not have started. Wait, I said 4 people get the credit. So, who is fourth one? Well, who is going to write this blog despite being very busy, oh sorry lazy, huh ?
     Now , more importantly what's this blog going to be about? So as the name suggests, this is not going to be about something in particular. I will write about all crazy stuff which I see around me, something I feel is worth sharing with you. I am also planning to write about some programming related stuff , whenever I learn something new and good (inspired by Saheel , demanded by Sujit ).
     I'll try to be regular on this blog, but past experiences have proved when it comes to regularity, I can not be trusted. so let's see how long I can continue this .
     I guess, that's enough for a "brief" intro.
Hope you like it. Your comments and suggestions are always welcome.