Fermat’s Little Theorem

Statement:

Let p be a prime then ap ≡ a (mod p), for any natural number a.

Proof using Modular Arithmetic:

Firstly, we need to discuss Wilson’s theorem. This states:

(p-1)! ≡ -1 (mod p) is p is prime.

We must first prove this theorem:

If p is prime, then 1, 2, …, p-1 are invertible mod p. Now we can pair each of these numbers with its inverse (for example 3 with 4 in mod 11). The only elements that cannot be paired with a different number are 1 and -1, which are self-inverses, as shown below:

Screen Shot 2017-01-02 at 6.30.37 PM.png

Now (p-1)! is a product of (p-3)/2 inverse pairs together with -1 and 1, whose product is -1.

So (p-1)! ≡ -1 (mod p).

Back to the proof of Fermat’s Little Theorem.

The statement of Fermat’s Little Theorem is equivalent to ap-1 ≡ 1 (mod p) if a ≢ 0 (mod p).

Consider the numbers a, 2a, …., (p-1)a. These are each distinct mod p and so they are congruent to 1, 2, …., (p-1) (mod p) in some order.

 Hence a·2a···(p-1)a ≡ 1·2···(p-1) (mod p).

So ap-1(p-1)! ≡ (p-1)!.

And therefore ap-1 ≡ 1 (mod p).

We can extend this to a≡ a (mod p) as shown below:

When a ≡ 0 (mod p): 0≡ 0 (mod p). So a≡ a (mod p).

When a ≢ 0 (mod p): We can multiply through by a, as a and p are coprime. Then we get a≡ a (mod p), as required.

Hence, we have proved Fermat’s Little Theorem, a very important result in number theory.

M x

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s