Fermat’s Little Theorem

A French lawyer at the Parlement of Toulouse, and amateur (means lover of) Mathematician in 17th century, called Pierre de Fermat proposed the following statement:

If p is a prime number, then for any integer n, the number n^{p} − n is an integer multiple of p

This post is dedicated to provide the proof of statement

Case 1: p is the divisor of n. Lets assume n = pk since \frac{n^p - n}{p} = \frac{n(p-1)}{p} = k(p - 1)

Case 2: p is not the divisor of n, which indirectly means p and n are relatively prime numbers. We provide the proof with the help of numbers n.2n.3n.4n.\dots (p-1)n

Here the key point is :

r_1 = \bmod(n,p)

r_{2} = \bmod(2n,p)

\dots

r_{p-1} = \bmod(n(p-1),p)

All of these reminders, which are r_{1}, r_{2} \dots r_{p-1} equals to different values.

The reason is quite straightforward! Since n and p are relatively numbers, multiple of n, -which is less than p and represented by A- can not provide this equation: An = pB for integer B. Let's try to prove this claim as well. If we can show that equation An = pB \rightarrow \frac{A}{B} = \frac{p}{n} does not hold, it contradicts and our claim would be proved by well-known method, called contradiction.

Here is the point: since p and n are relatively prime numbers, they don't have any common divisor. On the other hand, since A is less than p by problem definition, they must have one to satisfy this equation, nevermore there is no. So, equation contradicts and now we are sure that, we can not get same reminder of p for numbers k.n and k.n + A.n -where A is less than p.

After this proof, we need to keep going on. Before that, please notice that set of [r_{1}, r_{2}, r_{3}, \dots r_{p-1}] is equivalent to set of [0, 1, 2 \dots p-1], since each of those reminders has to be unique as we proved by contradiction.

Here we go. The sign " x | y " means that "x divides y".

n = p.k_{1} + r_{1} \rightarrow p | (n - r_{1})

2n = p.k_{2} + r_{2} \rightarrow p | (2n - r_{2})

3n = p.k_{3} + r_{3} \rightarrow p | (3n - r_{3})

\dots

(p-1)n = p.k_{p-1} + r_{p-1} \rightarrow p | ( (p-1)n - r_{p-1})

Small Theorem
Let a, b, c, d and p are integers such that, p | (a - b) and p | (c - d). Then, p | (ac - bd)

Small Proof
Since we have ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d), small proof is complete.

to the end...
Here, we use this small proof to conclude Fermat's Little Theorem.

Since p | n - r_{1} and p |2n - r_{2} we can say that:

p | [n . 2n - r_1 . r_2] \rightarrow p | [2n^{2} - r_{1}r_{2}]

Here, we can also include 3n - r_3 with our new value, since p divides both of them:

p | [3n . 2n^{2} - r_{3} . r_{2} . r_{1}]

\dots

As you can realize, we can add all numbers up to (n - 1)p

p | [n . 2n . 3n \dots (p - 1)n - r_1 . r_2 . r_3 \cdots r_{p-1}]

\rightarrow p | [(p - 1)!n^{p-1} - r_{1} . r_{2} . \cdots r_{p-1}]

\rightarrow p | [(p - 1)!n^{p-1} - (p - 1)!]

\rightarrow p | [(p - 1)! (n^{p-1} - 1)]

\rightarrow p | [1 . 2 . 3 \dots (p - 1) . (n^{p-1} - 1)]

Since p is a prime number and it is not divisible with numbers in between [1, p-1], it has to be divisor of n^{p-1} - 1 which concludes the proof.

p | (n^{p-1} - 1) \rightarrow p | (n^{p} - p)

References: