Le petit théorème de Fermat et son corollaire

Soit $a \in \mathbb{Z}$ un entier relatif et $p \in \mathbb{P}$ un nombre premier.

Petit théorème de Fermat

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) $$

Démonstration

Par raisonnement

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.

Les sept étapes de la démonstration

introduction de l'ensemble $ E $

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) $$

introduction de l'ensemble $ aE $

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\}$$

introduction des restes $ R_i $

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$.

tous les éléments $ R_i $ sont distincts (raisonnement par l'absurde)

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) $$

bijection entre $ e_i $ et $ R_i $

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] $$

multiplication des $ ae_i $ et des $ R_i $

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) $$

conclusion

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] $$

Corollaire

Soit $a \in \mathbb{Z}$ un entier relatif et $p \in \mathbb{P}$ un nombre premier.

Deux cas se présentent :

Si $ p $ ne divise pas $ a $

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^*}, $$

En multipliant les deux membres par $ a $ :

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

Si $ p $ divise $ a $

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] $$

Conclusion

Dans tous les cas,

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

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

Par récurrence

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) $$

Calcul du premier terme

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.

Vérification de l'hérédité

Dans l'ensemble des entiers naturels $ : \mathbb{N} $

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.

Dans l'ensemble des entiers relatifs : $ \mathbb{Z} $

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.

Conclusion

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 $p $ ne divise pas $a$

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] $$

Le petit théorème de Fermat et son corollaire

Démonstration

Par raisonnement

Les sept étapes de la démonstration

Corollaire

Par récurrence

Calcul du premier terme

Vérification de l'hérédité

Dans l'ensemble des entiers naturels \( : \mathbb{N} \)

Dans l'ensemble des entiers relatifs : \( \mathbb{Z} \)

Conclusion