The Notebook

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:

Ifpis a prime number, then for any integern, the numbern^{p} − nis an integer multiple ofp

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)**
proof is complete.

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

Since ** p | n - r_{1}** and ** p |2n - r_{2}**

** 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:*