Soit \(a \in \mathbb{Z}\) un entier relatif et \(p \in \mathbb{P}\) un nombre premier.
Le petit théorème de Fermat nous dit que :
$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad (Fermat) $$
Corollaire du petit théorème de Fermat
Et seulement si \( 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 (corollaire)\bigr) $$
Soit \(a \in \mathbb{Z}\) un entier relatif et \(p \in \mathbb{P}\) un nombre premier avec \( p \nmid a \).
Cette démonstration étant assez longue, nous l'avons scindée en différentes étapes successives.
Comme \(p \) est premier et que \( p \nmid a \),
On sait par le lien de primalité entre un nombre premier et tout entier relatif que :
$$ \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 $$
Soit :
$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 \qquad (1) $$
Considérons un ensemble \(E \) des nombres \( e_i \) avec :
$$ \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\}$$
\(p \) ne divisant aucun nombre inférieur à lui-même, alors :
$$\forall e_i, \enspace p \nmid e_i $$
Comme \(p \) est premier et que \(p \nmid e_i \), alors toujours par le lien de primalité entre un nombre premier et tout entier relatif, \(p \) et \(e_i\) sont premiers entre eux.
$$\forall e_i, \enspace p \nmid e_i \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p \wedge e_i = 1 \qquad (2) $$
Grâce aux relations \( (1) \) et \( (2) \), on a :
$$ \Biggl \{ \begin{align*} a \wedge p = 1 \qquad (1) \\ \forall e_i, \enspace e_i \wedge p = 1 \qquad (2) \end{align*} $$
Or, par le corollaire du théorème de Bézout, on sait que :
$$ \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 $$
Par conséquent :
$$ \forall e_i, \enspace p \wedge ae_i = 1 \qquad (3) $$
On considère alors un nouvel ensemble \(aE\) des nombres \( a e_i \) qui sont tous premiers deux à deux avec \( 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\}$$
On associe maintenant pour chaque \( a e_i \) un reste \( R_i\) de la division euclidienne par \( 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) $$
Et comme \(p \nmid ae_i\),
$$ \exists q \in \mathbb{N}, \enspace ae_i = pq + R_i$$
Grâce aux propriétés du \( PGCD \), on a :
$$ \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 PGCD(a, b) = PGCD(b, R) $$
Dans notre cas cela nous donne l'équivalence :
$$ ae_i = pq + R_i \Longrightarrow PGCD(ae_i, p) = PGCD(p, R_i)$$
Soit,
$$ ae_i \wedge p = p \wedge R_i \qquad (5) $$
Or, grâce à \( (3)\) :
$$ ae_i \wedge p = 1 \qquad (3) $$
Alors, grâce à \( (3)\) et \( (5)\),
$$ p \wedge R_i = 1 $$
Le nombre \( p\) est aussi premier avec chacun des restes \( R_i\).
Or, on a vu plus haut qu'avec \( (4)\) :
$$ 1 \leqslant R_i \leqslant (p-1) $$
Alors : \( R_i \in E\).
Prenons deux éléments distincts \( ae_i \) et \( ae_j \) de l'ensemble \( aE \). On a l'implication suivante :
$$ 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*} $$
Nous allons raisonner par l'absurde en supposant que \( R_i = R_j\). Alors dans ce cas :
$$ 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) $$
Or, comme grâce à \( (1) \), on sait que :
$$ a \wedge p = 1 \qquad (1) $$
D'après le théorème de Gauss, on sait que :
$$ \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 $$
Avec nos hypothèses, cela voudrait dire que :
$$ 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) $$
Or, comme :
$$ \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) $$
Et on l'a vu avec \( (2) \) :
$$\forall e_i, \enspace p \nmid e_i \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p \wedge e_i = 1 \qquad (2) $$
Donc \( p \) ne divise aucun nombre dans l'intervalle \( [\![1, (p-1) ]\!] \), et de fait non plus dans son intervalle miroir \( [\![-(p -1), -1 ]\!] \).
À ce stade, la seule possibilité pour satisfaire \( (6)\) serait que :
$$ 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 $$
Ce qui est impossible car cela contredie l'hypothèse de départ que \( ae_i \neq ae_j\).
Par conséquent, on a :
$$ e_i \neq e_j \hspace{0.2em} \Longrightarrow \hspace{0.2em} R_i \neq R_j \qquad (7) $$
On l'a vu plus haut, chaque reste \( R_i \) appartient tout comme les \( e_i \) à l'ensemble \( E \).
$$ \Biggl \{ \begin{align*} e_i \in E\\ R_i \in E \end{align*} \hspace{0.2em} $$
De plus, avec \( (7) \) on voit que pour chaque \( e_i \) distinct correspond un \( R_i \) distinct.
Cela veut dire qu'il y a une bijection (une relation de \( 1 \) pour \( 1\) dans les deux sens) entre les éléments \( e_i\) et \( R_i\).
$$ e_i \longleftrightarrow R_i $$
$$ E \longleftrightarrow E $$
À chaque élément \( e_i \) correspond un \( R_i \), mais pas nécessairement dans le même ordre.
Par exemple, pour \( 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\}$$
Soit une correspondance de \( 1\) pour \( 1\) entre les \(e_i\) et \( R_i\) :
$$ 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\}$$
En reprenant l'expression \( (4) \), on a :
$$ \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) $$
Soit une série de 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] $$
On sait par the properties of congruences 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] $$
Dans notre cas, en effectuant la multiplication des \( ae_i \) et des \( R_i \) :
$$ \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] $$
Comme il existe \((p-1)\) éléments distincts dans l'ensemble \(E\) pour les \(e_i\), ainsi que \((p-1)\) éléments distincts dans le même ensemble \(E\) pour les \(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) $$
Alors, avec \( (8) \) et les propriétés des congruences, on peut voir que \(p / (a^{p-1} - 1)(p-1)! \).
Mais comme \(p \nmid (p-1)! \) (car il n'a aucun diviseur commun avec aucun des \(e_i \) de \(E \)), par conséquent \(p / (a^{p-1} -1) \).
Soit,
$$ (a^{p-1} -1) \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$
$$ a^{p-1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$
Et finalement,
$$ \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] $$
Soit \(a \in \mathbb{Z}\) un entier relatif et \(p \in \mathbb{P}\) un nombre premier.
Deux cas se présentent :
Alors, avec le petit théorème de Fermat, on a :
$$ p \nmid a \Longrightarrow a^{p-1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$
Or, on sait par les propriétés des 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] $$
En multipliant les deux membres par \( a \) :
$$ a^{p} \equiv a \hspace{0.2em} \bigl[p\bigr] $$
Dans ce cas,
$$ 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] $$
Dans tous les cas,
$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] $$
Soit \(a \in \mathbb{Z}\) un entier relatif et \(p \in \mathbb{P}\) un nombre premier.
Essayons de montrer que la proposition suivante \((P_a)\) est vraie :
$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad (P_a) $$
Vérifions que c'est bien vrai pour le premier terme, c'est-à-dire pour \(a = 0 \).
$$ 0^p \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$
\((P_0)\) est vraie.
Soit \( k \in \mathbb{N} \) un entier naturel.
On suppose que la proposition \((P_k)\) est vraie pour tout \( k \).
$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (P_{k}) $$
Vérifions que c'est bien le cas pour \((P_{k + 1})\).
$$ (k+1)^p \equiv k+1 \hspace{0.2em} \bigl[p\bigr] \qquad (P_{k + 1}) $$
Calculons \( (k+1)^p\).
Avec le binome de Newton, on sait que :
$$\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 $$
Soit ici,
$$ (k+1)^p = k^p + \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} + 1 \qquad (1) $$
Or, pour tout \( p, i \), avec \( 1 \leqslant i \leqslant p \) on peut appliquer la formule du pion :
$$ \binom{p}{i} = \frac{p}{i} \binom{p-1}{i-1} $$
$$ i \binom{p}{i} = p \binom{p-1}{i-1} $$
Or, on sait par le théorème de Gauss que :
$$ \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 $$
Dans notre cas,
$$ \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} $$
Si \( p \) divise le binôme \( \binom{p}{i} \), alors \( p \) divise aussi le membre central de \( (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} avec \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.05em} \mathbb{N} \)} \hspace{0.1em} + 1 \qquad (1) $$
Soit,
$$ \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} \equiv 0 \bigl[p\bigr] $$
Et comme par hypothèse de recurrence,
$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (P_k) $$
En résumé, on a les congruences suivantes pour le calcul de \( (k+1)^p \) :
$$ (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 $$
On a alors par somme des congruences que :
$$ (k+1)^p \equiv k + 1 \bigl[p\bigr] \qquad (P_{k + 1}) $$
Par conséquent, \((P_{k + 1})\) est vraie.
Ici, il s'agit de faire la même chose dans le sens contraire, pour vérifier que c'est aussi vrai dans \( \mathbb{Z}\).
Nous allons donc cette fois vérifier que \((P_{k - 1})\) est vraie.
$$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$
Calculons \( (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\) étant un nombre premier par hypothèse, il sera toujours impair, donc on aura :
$$ (k-1)^p = k^p + \sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} -1 \qquad (1') $$
De la même manière, si \( p \) divise le binôme \( \binom{p}{i} \), alors \( p \) divise aussi le membre central de \( (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} avec \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.05em} \mathbb{Z} \)}\hspace{0.2em} - 1 \qquad (1') $$
Même si ce membre central comporte une alternance de termes négatifs et positifs, son quotient général \( Q \) reste dans \( \mathbb{Z} \).
Et on aura aussi, tout comme précédemment :
$$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (P_k) $$
Soit pour résumer :
$$ (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 $$
Et finalement,
$$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$
\((P_{k - 1})\) est vraie.
La proposition \((P_a)\) est vraie pour son premier terme \(a_0 = 0\) et est héréditaire de proche en proche pour tout \(k \in \mathbb{Z}\), de manière croissante et décroissante.
Par le principe de récurrence, elle ainsi est vraie pour tout \(a \in \mathbb{Z}\).
Soit finalement,
$$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] $$
On a alors l'équivalence :
$$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p/(a^p -a) $$
Puis en factorisant par \(a\),
$$ p/(a^p -a) \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} p/a(a^{p-1} -1) \qquad (2) $$
Si on a comme hypothèse supplémentaire que \( p \nmid a \) :
On sait par le lien de primalité entre un nombre premier et tout entier relatif que :
$$ \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 $$
Alors,
$$ a \wedge p = 1 \qquad (3) $$
De plus, avec le théorème de Gauss, on sait que :
$$ \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 $$
Dans notre cas, \( (2) \) combinée avec \( (3) \) donne :
$$ 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] $$
Soit finalement,
$$ \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] $$