Let \(a \in \mathbb{Z}\) be an integer and \(p \in \mathbb{P}\) a prime number.
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) $$
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) $$
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.
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) $$
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\}$$
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\).
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.
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] $$
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) $$
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] $$
Let \(a \in \mathbb{Z}\) be an integer and \(p \in \mathbb{P}\) a prime number.
Two cases arise:
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^*}, $$
$$ \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] $$
Multiplying both members by \( a \):
$$ a^{p} \equiv a \hspace{0.2em} \bigl[p\bigr] $$
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] $$
In any case,
$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] $$
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) $$
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.
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.
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.
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 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] $$
Go to the top of the page
