Fermat’s little Theorem

Fermat’s little theorem: Let p be a prime. Then a^p-a is a multiple of p. In other words a^p is congruent to a mod p.

Proof: We will use Induction. For a=1 we have a^p-a=1^p-1=1-1=0. 0 is a multiple of p.

Now we assume, that the theorem works for a.

Last but not least, we have to show that a+1 works.  We have  (a+1)^p-(a+1)=(a+1)^p-a-1. Now we use the binomial theorem:

Screen Shot 2014-12-20 at 11.52.24 AM

We know that a^p-a is a multiple of p. Every summand of the sum is a multiple of p as well. It follows, that the theorem works for a+1 as well.

This proves the theorem.

Advertisements

One thought on “Fermat’s little Theorem

  1. Dominic Pepitone

    This site is just gret. I’ve search these info a whole lot and I
    realised that is good written, easy to comprehend.
    I congratulate you for this article that I am going to tell to the
    people friends. I ask you to go to the gpa-calculator.co site
    where each university student or learner can find ratings gpa rating.
    Success!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s