The fermat's small theorem and its corollary

Let $a \in \mathbb{Z}$ be an integer and $p \in \mathbb{P}$ a prime number.

The fermat's small theorem

The fermat's small theorem tells us that:

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$

$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad (Fermat) $$

Corollary of the fermat's small theorem

And only if $ p \nmid a $:

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$

$$ p \nmid a \Longrightarrow a^{p-1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] \qquad \bigl(Fermat \enspace (corollary)\bigr) $$

Demonstration

By reasoning

Let $a \in \mathbb{Z}$ be an integer and $p \in \mathbb{P}$ a prime number with $ p \nmid a $.

This demonstration being a bit long, we have splitted it into several steps.

The seven steps of the demonstation

introducing the $ E $ set

As $p $ is a prime number and $ p \nmid a $,

We know by the coprimity link between a prime number and an integer that:

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, \enspace p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$

So:

$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 \qquad (1) $$

Let consider a $E $ set of $ e_i $ numbers with:

$$ \forall i \in [\![1, (p-1) ]\!], \enspace e_i = i$$

$$ E = \Bigl \{ e_1, e_2 , \hspace{0.2em} ... \hspace{0.2em}, e_{i} \Bigr\} = \Bigl \{ 1, 2 , \hspace{0.2em} ... \hspace{0.2em}, (p-1) \Bigr\}$$

Having $p $ not dividing any numbers lower thant it, then:

$$\forall e_i, \enspace p \nmid e_i $$

As $p $ is prime and $p \nmid e_i $, so still with the coprimity link between a prime number and an integer, $p $ and $e_i$ are coprimes.

$$\forall e_i, \enspace p \nmid e_i \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p \wedge e_i = 1 \qquad (2) $$

introducing the $ aE $ set

Thanks to both relations $ (1) $ and $ (2) $, we do have:

$$ \Biggl \{ \begin{align*} a \wedge p = 1 \qquad (1) \\ \forall e_i, \enspace e_i \wedge p = 1 \qquad (2) \end{align*} $$

Now, by the Bézout's theorem corollary, we do know that:

$$ \forall (a, b, n) \in \hspace{0.05em} \mathbb{Z}^3, $$

$$ \Biggl \{ \begin{align*} a \wedge n = 1 \\ b \wedge n = 1 \end{align*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} ab \wedge n = 1 $$

Consequently:

$$ \forall e_i, \enspace p \wedge ae_i = 1 \qquad (3) $$

We now consider a new set, called $aE$, of $ a e_i $ numbers which are all coprimes with $ p $.

$$ aE = \Bigl \{ a e_1, a e_2 , \hspace{0.2em} ... \hspace{0.2em}, a e_{i} \Bigr\} = \Bigl\{ a, 2a , \hspace{0.2em} ... \hspace{0.2em}, a(p-1) \Bigr\}$$

introducing the $ R_i $ remainders

Let match for each number $ a e_i $, a $ R_i$ remainder of the Euclidian division by $ p $.

$$ \forall ae_i , \enspace \exists R_i, \enspace 1 \leqslant R_i \leqslant (p-1), \enspace ae_i \equiv R_i \hspace{0.2em} [p] \qquad (4) $$

And as $p \nmid ae_i$,

$$ \exists q \in \mathbb{N}, \enspace ae_i = pq + R_i$$

Thanks to the properties of the $ GCD $, we do have:

$$ \forall (a, b, q) \in (\mathbb{N})^3, \enspace a > b, \enspace \forall R \in \mathbb{N^*}, \enspace 0 < R < b, $$

$$ a = bq + R \Longrightarrow GCD(a, b) = GCD(b, R) $$

In our case, it gave us the folloning equivalence:

$$ ae_i = pq + R_i \Longrightarrow PGCD(ae_i, p) = PGCD(p, R_i)$$

So,

$$ ae_i \wedge p = p \wedge R_i \qquad (5) $$

But, thanks to $ (3)$ :

$$ ae_i \wedge p = 1 \qquad (3) $$

Therefore, thanks to $ (3)$ and $ (5)$,

$$ p \wedge R_i = 1 $$

The number $ p$ is also coprime with each $ R_i$ remainder.

Well, we have seen above with $ (4)$ that:

$$ 1 \leqslant R_i \leqslant (p-1) $$

So then: $ R_i \in E$.

each $ R_i $ elements are all distincts (by absurd reasoning)

Let take two distincts elements $ ae_i $ and $ ae_j $ of the $ aE $ set. We do have the following implication:

$$ ae_i \neq ae_j \hspace{0.2em} \Longrightarrow \hspace{0.2em} \Biggl \{ \begin{align*} ae_i \equiv R_i \hspace{0.2em} \bigl[p\bigr] \\ ae_j \equiv R_j \hspace{0.2em} \bigl[p\bigr] \end{align*} $$

Let absurdly assume that $ R_i = R_j$. In this case:

$$ R_i = R_j \hspace{0.2em} \Longrightarrow \hspace{0.2em} ae_i \equiv ae_j \hspace{0.2em} \bigl[p\bigr]$$

$$ a(e_i - e_j) \equiv 0 \hspace{0.2em} \bigl[p\bigr] \hspace{0.2em} \Longrightarrow \hspace{0.2em} p/a(e_i - e_j) $$

But, as we know thanks to $ (1) $ that:

$$ a \wedge p = 1 \qquad (1) $$

From The Gauss' theorem, we know that:

$$ \forall (a, b, c) \in (\mathbb{Z})^3,\enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

With our hypotheses, this would mean that:

$$ p / a(e_i - e_j) \enspace et \enspace a \wedge p = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p / (e_i - e_j) \qquad (6) $$

Well, as:

$$ \Biggl \{ \begin{align*} 1 \leqslant e_i \leqslant (p-1) \\ 1 \leqslant e_j \leqslant (p-1) \end{align*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} (-p + 2) \leqslant e_i - e_j \leqslant (p-2) $$

And we have seen it with $ (2) $:

$$\forall e_i, \enspace p \nmid e_i \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p \wedge e_i = 1 \qquad (2) $$

Therefore $ p $ does not divide any number on the following interval: $ [\![1, (p-1) ]\!] $, and in fact none of its mirror interval: $ [\![ -(p -1), -1 ]\!] $.

At thsi stage, the only possibility to satisfy $ (6)$ would be:

$$ p / (e_i - e_j) \hspace{0.2em} \Longrightarrow \hspace{0.2em} e_i - e_j = 0 $$

$$ p / (e_i - e_j) \hspace{0.2em} \Longrightarrow \hspace{0.2em} e_i = e_j $$

Which is impossible because it would refute our beginning hypothesis which was that: $ ae_i \neq ae_j$.

As a result, we do have the following conclusion:

$$ e_i \neq e_j \hspace{0.2em} \Longrightarrow \hspace{0.2em} R_i \neq R_j \qquad (7) $$

Each $R_i$ remainders are all distincts.

bijection between $ e_i $ and $ R_i $ elements

We have seen above that each $ R_i $ remainder as each $ e_i $ elements belonged to the $ E $ set.

$$ \Biggl \{ \begin{align*} e_i \in E\\ R_i \in E \end{align*} \hspace{0.2em} $$

Morover, with $ (7) $ we found out that each distinct $ e_i $ matched a distinct $ R_i $.

This means that it exists a bijection (one-to-one relationship in both directions) between $ e_i$ and $ R_i$ elements.

$$ e_i \longleftrightarrow R_i $$

$$ E \longleftrightarrow E $$

For each $ e_i $ corresponds a $ R_i $ elements, But not necessarily in the right order.

For example, for the values: $ p = 7, a = 9$ :

$$(e_i) \enspace \enspace E = \Bigl \{ 1, 2 , 3, 4, 5 , 6, 7, 8 \Bigr\}$$

$$ (ae_i) \enspace \enspace aE = \Bigl \{ 5, 10 , 15, 20, 25, 30, 35, 40 \Bigr\}$$

$$ (R_i) \enspace \enspace E = \Bigl \{ 5, 1 , 6, 2, 7, 3 , 8, 4 \Bigr\}$$

Thus a one-to-one correspondance between $e_i$ and $ R_i$ elements:

$$ E = \Bigl \{ e_1 = r_2, \enspace e_2 =r_4, \enspace e_3 = r_6, \enspace e_4 = r_8, \enspace e_5 = r_1, \enspace e_6 = r_3, \enspace e_7 = r_5, \enspace e_8 = r_7 \Bigr\}$$

Let write again the expression $ (4) $:

$$ \forall ae_i , \enspace \exists R_i, \enspace 1 \leqslant R_i \leqslant (p-1), \enspace ae_i \equiv R_i \hspace{0.2em} [p] \qquad (4) $$

So, a such serie of congruences:

$$ ae_1 \equiv R_1 \hspace{0.2em} [p], \enspace ae_2 \equiv R_2 \hspace{0.2em} [p], \enspace ... , \enspace ae_i \equiv R_i \hspace{0.2em} [p] $$

The $ ae_i $ and $ R_i $ elements product

We know from the properties of congruences que :

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall (a', b') \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall n \in \mathbb{N^*}, $$

$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a a' \equiv b b' \hspace{0.2em} [n] $$

In our case, performing both $ ae_i $ and $ R_i $ inner elements products:

$$ \prod_{i = 1}^{p-1} ae_i \equiv \prod_{i = 1}^{p-1} R_i \hspace{0.2em} \bigl[p\bigr] $$

$$ (ae_1 \times ae_2 \hspace{0.2em} \times ... \times \hspace{0.2em} ae_i) \equiv (R_1 \times R_2 \hspace{0.2em} \times ... \times \hspace{0.2em} R_i \hspace{0.2em} ) \bigl[p\bigr] $$

Having $(p-1)$ distincts elements inside the $E$ set for $e_i$, and $(p-1)$ distincts elements inside the same $E$ set for $R_i$:

$$ a^{p-1}(p-1)! \equiv (p-1)! \hspace{0.2em} \bigl[p\bigr] $$

$$ a^{p-1}(p-1)!- (p-1)! \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$

$$ (a^{p-1} - 1)(p-1)! \equiv 0 \hspace{0.2em} \bigl[p\bigr] \qquad (8) $$

conclusion

Finally, with $ (8) $ and the properties of congruences, it is clear that $p / (a^{p-1} - 1)(p-1)! $.

But as $p \nmid (p-1)! $ (because it does not anu common divisor with any of the $e_i $ of the $E $ set), therefore $p / (a^{p-1} -1) $.

So,

$$ (a^{p-1} -1) \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$

$$ a^{p-1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$

And finally,

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$

$$ p \nmid a \Longrightarrow a^{p-1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$

Corollary

Let $a \in \mathbb{Z}$ be an integer and $p \in \mathbb{P}$ a prime number.

Two cases arise:

If $ p $ does not divide $ a $

So, with the Fermat's small theorem, we do have:

$$ p \nmid a \Longrightarrow a^{p-1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$

But, from the properties of congruences we know that:

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall (a', b') \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall n \in \mathbb{N^*}, $$

Multiplying both members by $ a $:

$$ a^{p} \equiv a \hspace{0.2em} \bigl[p\bigr] $$

If $ p $ divides $ a $

In this case,

$$ p/a(a^{p-1} - 1) \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p/(a^p -a) $$

$$ a^{p} \equiv a \hspace{0.2em} \bigl[p\bigr] $$

Conclusion

In any case,

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$

$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] $$

By recurrence

Let $a \in \mathbb{Z}$ be an integer and $p \in \mathbb{P}$ a prime number.

Let show that the following statement $(P_a)$ is true:

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$

$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad (P_a) $$

First term calculation

Let verify if is true for the first term, that is to say for $ a = 0 $.

$$ 0^p \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$

$(S_0)$ is true.

Heredity

In the natural numbers set

Let $ k \in \mathbb{N} $ be a natural number.

Let us assume that $(S_k)$ is true for all $ k $.

$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_{k}) $$

We will verify that is also the case for $(S_{k + 1})$.

$$ (k+1)^p \equiv k+1 \hspace{0.2em} \bigl[p\bigr] \qquad (S_{k + 1}) $$

Let us calculate $ (k+1)^p$.

With the Newton's binomial, we know that:

$$\forall n \in \mathbb{N}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{R}^2,$$

$$ (a + b)^n = \sum_{p = 0}^n \binom{n}{p} a^{n-p}b^p $$

So,

$$ (k+1)^p = k^p + \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} + 1 \qquad (1) $$

Well, for all $ p, i $, with $ 1 \leqslant i \leqslant p $ we can apply the binomial's pawn formula :

$$ \binom{p}{i} = \frac{p}{i} \binom{p-1}{i-1} $$

$$ i \binom{p}{i} = p \binom{p-1}{i-1} $$

But, we know by the Gauss' theorem that:

$$ \forall (a, b, c) \in \hspace{0.05em} \mathbb{Z}^3, \enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

In our case,

$$ \forall i \in \hspace{0.05em} 1 \leqslant i \leqslant (p-1),$$

$$ p / i\binom{p}{i} \enspace et \enspace p \wedge i = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p / \binom{p}{i} $$

If $ p $ divides the $ \binom{p}{i} $ binom, then $ p $ also divides the central member of $ (1) $.

$$ (k+1)^p = k^p + \enspace \underbrace{\sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} } _\text{$ = \hspace{0.2em} pQ, \hspace{0.4em} with \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.05em} \mathbb{N} $} \hspace{0.1em} + 1 \qquad (1) $$

So,

$$ \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} \equiv 0 \bigl[p\bigr] $$

And as our recurrence hypothesis is:

$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_k) $$

These are all the congruences for the $ (k+1)^p $ calculation:

$$ (k+1)^p = \underbrace{ k^p } _\text{$ \equiv \hspace{0.2em} k \hspace{0.2em} [p] $} + \enspace \underbrace{\sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} } _\text{$ \equiv \hspace{0.2em} 0 \hspace{0.2em} [p] $} \hspace{0.2em} + 1 $$

We then have by addition of the congruences:

$$ (k+1)^p \equiv k + 1 \bigl[p\bigr] \qquad (S_{k + 1}) $$

Thus, $(S_{k + 1})$ est vraie.

In the relative numbers set

Here, we have to prove it in the contrary direction, to verify if it is still true inside the $ \mathbb{Z}$ set.

In other words, let verify that $(P_{k - 1})$ is true.

$$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$

Let us calculate $ (k-1)^p $.

$$ (k-1)^p = k^p + \sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} + (-1)^p \qquad (P_{k - 1}) $$

$p$ being a prime number by hypothesis, it will always be odd, and then:

$$ (k-1)^p = k^p + \sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} -1 \qquad (1') $$

Likewise, if $ p $ divise the $ \binom{p}{i} $ binom, then $ p $ also divides the central member of $ (1') $ :

$$ (k-1)^p = k^p + \enspace \underbrace{\sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} } _\text{$ = \hspace{0.2em} pQ, \hspace{0.4em} with \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.05em} \mathbb{Z} $}\hspace{0.2em} - 1 \qquad (1') $$

Even if this central member contains an alternance of positive and negative numbers, its general quotient $ Q $ remains inside the $ \mathbb{Z} $ set.

We will also, like previously:

$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_k) $$

So these are all the congruences for the $ (k-1)^p $ calculation:

$$ (k-1)^p = \underbrace{ k^p } _\text{$ \equiv \hspace{0.2em} k \hspace{0.2em} [p] $} + \enspace \underbrace{\sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} } _\text{$ \equiv \hspace{0.2em} 0 \hspace{0.2em} [p] $} \hspace{0.2em} - 1 $$

And finally,

$$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$

$(P_{k - 1})$ est vraie.

Conclusion

The statement $(P_a)$ is true for its fisrt term $a_0 = 0$ and it's hereditary from terms to terms for all $k \in \mathbb{Z}$, upwards and downwards.

By the recurrence principle, that statement is true for all $a \in \mathbb{Z}$.

And finally,

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$

$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] $$

We then have the following equivalence:

$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p/(a^p -a) $$

Now, factorizing by $a$,

$$ p/(a^p -a) \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p/a(a^{p-1} -1) \qquad (2) $$

If $p $ does not divide $a$

If we add the extra hypothesis that $ p \nmid a $:

We know by the coprimity link between a prime number and an integer that:

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, \enspace p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$

So,

$$ a \wedge p = 1 \qquad (3) $$

Moreover, with Gauss' theorem, we know that:

$$ \forall (a, b, c) \in \hspace{0.05em}\mathbb{Z}^3,\enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

In our case, $ (2) $ combined with $ (3) $ gives:

$$ p/a(a^{p-1} -1) \enspace et \enspace a \wedge p = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p/ (a^{p-1} -1) $$

$$ a^{p-1} -1 \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$

And finally,

$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$

$$ p \nmid a \Longrightarrow a^{p-1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$

The fermat's small theorem and its corollary

Demonstration

By reasoning

The seven steps of the demonstation

Corollary

By recurrence

First term calculation

Heredity

In the natural numbers set

In the relative numbers set

Conclusion