Proofs of Fermat's little theorem Details, Meaning Proofs of Fermat's little theorem Article and Explanation Guide

Proofs of Fermat's little theorem Guide, Meaning , Facts, Information and Description

This is a collection of proofs of Fermat's little theorem:

a^p = a (mod p)

for every prime number p and every integer a.

Note that it is enough to prove

a^{p − 1} = 1 (mod p)

for every integer a which is relatively prime to p (i.e. not a multiple of p). Multiplying with a then gives the above version of the theorem for those numbers a; for the multiples of p the above version is clear anyway.

Table of contents

1 A direct proof
2 A proof using group theory
3 Inductive proof with the binomial theorem
4 A proof using bracelets
5 A proof by counting base-n p-digits numbers

5.1 Count the numbers of base-n numbers with p digits
5.2 Notice that by rotating the digits, most numbers come in groups of p
5.3 Not always so ... (p has to be prime)
5.4 Numbers made from repeating single digit (like 777777) dont have friends
5.5 Conclusion:

6 A proof using dynamical systems
7 A second proof using Dynamical systems

A direct proof

We will assume a to be relatively prime to p. This proof will make use of our base a multiplied by all the numbers from 1 to p − 1. It turns out that if p is prime, the values 1a through (p − 1)a (modulo p) are just the numbers from 1 through p − 1 rearranged, a consequence of the following lemma. We then multiply all those numbers together, resulting in a formula from which the theorem follows.

Lemma: If a is relatively prime to p and x and y are integers such that xa = ya (mod p), then x = y (mod p).

Proof of lemma: xa = ya (mod p) means that p divides xa − ya = a (x − y). We know that a does not contain the prime factor p, so (x − y) must contain it, since the prime factorization is unique by the fundamental theorem of arithmetic. So p divides (x − y), which means x = y (mod p), which completes the proof of the lemma.

Proof of theorem: Consider the set P = {1a, 2a, 3a, ... (p − 1)a}. These numbers are different modulo p by the lemma, and none of them is zero modulo p (again by the lemma: 0a = ka (mod p) would imply 0 = k modulo p, but k is too small for that). So modulo p, the set P is the same as the set N = {1, 2, 3, ... (p − 1)}. So if we multiply the elements of these two sets together, we will get the same result modulo p:

1a * 2a * 3a * ... (p − 1)a = 1 * 2 * 3 * ... (p − 1) (mod p)

Regrouping the left side:

(1*2*3*...(p − 1)) * a^{p − 1} = 1*2*3*...(p − 1) (mod p)

Now we would like to cancel the common term (p − 1)factorial from both sides. This is allowed by the lemma, since p and (p − 1)! can have no factor in common, again by the fundamental theorem of arithmetic. Dividing out (p − 1)!, we get:

a^{p − 1} = 1 (mod p).

Q.E.D

A proof using group theory

Inductive proof with the binomial theorem

Here we use mathematical induction. First, the theorem is true for a=1, then one proves that that if it is true for a = k, it is also true for a = k + 1, concluding that the theorem is true for all a.

Before the main argument the following lemma is needed

(a + b)^p mod p = a^p + b^p mod p

when p is prime. The Binomial theorem tells us that

is, by the fundamental theorem of arithmetic, a multiple of p, so the whole term   is a multiple of p if 0 < i < p. This means the whole sum from i = 1 to i = p - 1 equals 0 mod p. So, (a + b)^p mod p indeed equals a^p + b^p mod p when p is prime.

Back to the proof of the theorem. We proceed now with the two induction steps.

Obviously, when a = 1, a^p mod p = a.
We assume for now that when a = k, the theorem is true, that is, we assume that k^p mod p = k, and see what happens when a = k + 1:

(k + 1)^p mod p

= k^p + 1^p mod p (by the statement shown above)

= k^p + 1 mod p.

Since we assumed that k^p mod p = k, we conclude that (k + 1)^p mod p = k + 1, which is what we wanted to demonstrate.

A proof using bracelets

Here is an interesting proof which involves very little symbolic mumbo-jumbo.

Let us say that I make closed bracelets out of open chains that consist of p coloured links, with a choice of a different colours; and that I can use the links in any combination. Now, since these are closed bracelets, if I give you one, but you will be able to rotate it at will. So the 9-link bicolor bracelet ABAABBBBB is the same as BBABAABBB (you can rotate the bracelet), but it is different from BBBBBAABA (you cannot reverse it or recolour it).

Some 9-link bracelets can be made from only one "directional" open chain, such as AAAAAAAAA; however, some can be made from more than one such chain (ABBABBABB, BABBABBAB, BBABBABBA all make the same bracelet).

If you tell me how many links a bracelet is to have (call this number p), how many different bracelets of that size can I make, and out of how many distinct open chains can I make each one? Since it is Fermat's Little Theorem we are trying to prove, let us restrict ourselves to cases where p is prime. Let us find the answer thus:

AAAA... and BBBB... and all a unicolor bracelets are special cases; these bracelets can be made out of only one (kind of) open chain.
Anything else can be made out of p different open chains. Proof: Take such a bracelet and open it as many ways as you can. Each way will be different, because of this (next argument is actually incomplete but hints at the general idea):
- Let us say it is a 7-link chain. Open it up and label the links abcdefg. Now if you opened it up in a different way, say between a and b, you would get the open chain bcdefga, and if the two were equal, we'd have a=b=c=d=e=f=g, which leads us to a unicolor bracelet, which was excluded. If instead you cut between c and d, we'd get a=c=e=g=b=d=f, which again leads to a unicolor bracelet. The only way it can come out even at any time is if we can find a number less than p that is coprime to p, but since p is prime, we can't!

So what do we have? We have a unicolor bracelets, each from one unicolor open chain; and the other a^p-a (multicolor) open chains make (a^p-a)/p bracelets, each from p open chains. This shows that p divides (a^p-a).

A proof by counting base-n p-digits numbers

Similar to the bracelet proof above.

Count the numbers of base-n numbers with p digits

In the following :

1.	`00000`
2.	`00001`
3.	`00002`
...
n.	`0000m`
n+1.	`00010`
n+2.	`00011`
...
n^p.	`mmmmm`

Total numbers .

Notice that by rotating the digits, most numbers come in groups of p

For example the numbers 82319, 23198, 31982, 19823 and 98231. THINK ROTATION! Every number is gotten from the previous one by taking the leftmost digit and putting it to the right.

Not always so ... (p has to be prime)

Well, lets think of numbers with 6 digits (). Most of these numbers will come in groups of 6 (for example: 456321, 563214, 632145, 321456, 214563, and 145623).

But what about 171717? After rotating the digits we get 717171. BUT AFTER ANOTHER ROTATION WE GET 171717, ALREADY COUNTED!.

Also look at 182182: after rotation we get 821821 and 218218, and that's it! Instead of 6 friends we got only 3.

This happens only when is composite, and the number is made up of similar parts.

If is prime, the rotaion cannot give us less then different numbers. So if is prime, the numbers indeed can be grouped in groups of .

Numbers made from repeating single digit (like 777777) dont have friends

There are exactly of these numbers. (11111, 22222, ... mmmmm).

Conclusion:

Total numbers (length p, base n) less those made of one repating digit, can be grouped in groups of p (if is prime) by rotation. Or: If is prime is divisible by .

A proof using dynamical systems

Here we prove the special case a = 2 using the fixed pointss of a 1D-map which is commonly encountered in dynamical systems.

Define the "tent" map:

f(x) = 1 - 2 |x| for x in the interval [-1, 1]

and consider the dynamical system x_n+1 = f(x_n), n = 0, 1, 2, ... If x₀ is chosen in the interval [-1,1], then all x_n will remain in that same interval.

The fixed points of f are -1 and 1/3.

If p is a prime number, then the p-iterated map f^p has 2^p fixed points which are solutions of:

x = 1 ± 2 ± 4 ± ... ± 2^p x

But two of these fixed points are –1 and 1/3. All the others must have period p, since any period would have to be divisor of p but the prime number p doesn't have any non-trivial divisors.

So, we have 2^p – 2 fixed points, forming disjoint orbits of period p. Then (2^p – 2)/p is a natural number, the number of orbits of period p. So p' divides 2p'' - 2.

Take this into account: numerical calculations must fail for great p due to rounding errors of the calculator or the computer.

A second proof using Dynamical systems

The following needs to be checked and cleaned up.

For any n we define in the interval (0,1) ->(0,1) ( ) closed

Tn(x) = FP(nx), x<1

Tn(x) = 1, x=1

FP: Fractional Part

Lemma 1: Let n be an integer greater than 1. The function Tn(x) has n fixed points in (0,1).

Lemma 2: Let a and b be positive integers. Then for all x belognig to (0,1):

Ta(Tb(x)) = Tab(x)

Using values a and p, we consider the p-periodic point of Ta. These p-periodic points are fixed points of Ta iterated p times, which is Ta^p. This has a^p fixed points. Of these, exactly a are fixed points of Ta.

Since p is prime the rest of them have minimal period p under Ta. This means that there are a^p-a points that have minimal period p. Since each point with minimal period p lies in an orbit p, there are (a^p-a)/p orbits of size p. Since this is an integer, we see that p divides (a^p-a).

This is an Article on Proofs of Fermat's little theorem. Page Contains Information, Facts Details or Explanation Guide About Proofs of Fermat's little theorem

Proofs of Fermat's little theorem Guide, Meaning , Facts, Information and Description

A proof using bracelets

Count the numbers of base-n numbers with p digits

Search Anything