French flag English flag
Index des cours

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.


  1. Petit théorème de Fermat
  2. 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) $$

  3. Corollaire du petit théorème de Fermat

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

  1. Par raisonnement

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


    1. Les sept étapes de la démonstration

      1. introduction de l'ensemble \( E \)
      2. Comme \(p \) est premier et que \( p \nmid a \),

        On sait par le lien de primalité entre deux nombres 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 avec par le lien de primalité entre deux nombres, \(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) $$


      3. introduction de l'ensemble \( aE \)
      4. 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 les propriétés des nombres premiers, 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\}$$

      5. introduction des restes \( R_i \)
      6. 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\).

      7. tous les éléments \( R_i \) sont distincts (raisonnement par l'absurde)
      8. 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) $$

      9. bijection entre \( e_i \) et \( R_i \)
      10. 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] $$


      11. multiplication des \( ae_i \) et des \( R_i \)
      12. 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) $$


      13. conclusion
      14. 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] $$


    2. Corollaire

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

      Deux cas se présentent :

      1. Si \( p \) ne divise pas \( a \)
      2. 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] $$

      3. Si \( p \) divise \( a \)
      4. 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] $$

      5. Conclusion
      6. Dans tous les cas,

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

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


  3. Par récurrence

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

    1. Calcul du premier terme

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


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

      1. Dans l'ensemble des entiers naturels \( : \mathbb{N} \)
      2. 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 (p, n) \in \hspace{0.05em}\mathbb{N}^2, \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.


      3. Dans l'ensemble des entiers relatifs : \( \mathbb{Z} \)
      4. 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.


    4. Conclusion

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


      1. Si \(p \) ne divise pas \(a\)
      2. Si on a comme hypothèse supplémentaire que \( p \nmid a \) :

        On sait par le lien de primalité entre deux nombres 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] $$

    Index des cours
    Retour en haut de page