Ce que peut produire un produit !

Dans cet article, je vous propose de voir comment un même artifice technique, emprunté à la théorie des groupes finis, permet d’établir les trois résultats suivants (p désigne un nombre premier) :

  • 1+\left(p-1\right)!\equiv0\pmod{p}                                                                                               (th. de Wilson)
  • Pour tout n\in\mathbb{N}, n^{p}\equiv n\pmod{p}                                                                          (petit th. de Fermat)
  • \exists k\in\mathbb{Z},\,k^2\equiv-1\pmod{p}\Leftrightarrow p=2 ou p\equiv1\pmod{4}                      (cas particulier critère d’Euler)

Avant d’entrer dans le vif du sujet, précisons les notations et rappelons quelques résultats.

1 – Rapide survol de l’anneau \mathbb{Z}/n\mathbb{Z} et du corps \mathbb{F}_p

Etant donné un entier n\geqslant2, la notation a\equiv b\pmod{n} indique que l’entier a est congru à l’entier b modulo n, ce qui signifie que n est un diviseur de a-b.

La congruence modulo n est une relation d’équivalence (réflexive, symétrique et transitive) dans \mathbb{Z}.

La classe d’équivalence de a\in\mathbb{Z} peut être notée \overline{a} (notation commode, mais ambigüe puisqu’elle n’indique pas quel est l’entier n sous-jacent).

L’ensemble des classes d’équivalence, noté \mathbb{Z}/n\mathbb{Z}, comporte n éléments (à savoir les \overline{k} pour k\in\mathbb{Z} tel que 0\leqslant k\leqslant n-1).

On définit deux opérations (notées + et \times) dans \mathbb{Z}/n\mathbb{Z} en posant, pour tout \left(k,\ell\right)\in\left\{ 0,\cdots n-1\right\} ^{2} :

    \[\overline{k}+\overline{\ell}=\overline{k+\ell}\qquad\text{et}\qquad\overline{k}\times\overline{\ell}=\overline{k\ell}\]

On s’assure de la validité de ces définitions en vérifiant que \overline{k+\ell} et \overline{k\ell} ne dépendent pas des entiers k et \ell choisis pour représenter ces classes.

Muni de ces deux opérations, l’ensemble \mathbb{Z}/n\mathbb{Z} devient un anneau commutatif, qui n’est intègre que si n est premier et qui, dans ce cas, est même un corps (tout élément autre que la classe nulle est inversible).

Lorsque p est premier, on note \mathbb{F}_{p} pour \mathbb{Z}/p\mathbb{Z} (“corps” se dit “field” en anglais, d’où le \mathbb{F}).

2 – Factorielle d’un groupe abélien fini

Soit G un groupe abélien fini (l’opération en vigueur dans G est notée multiplicativement).

Je propose de nommer factorielle de G et de noter G! le produit de tous les éléments de G.

Ainsi, en notant G=\left\{ a_{1},\cdots,a_{n}\right\} :

    \[G!=\prod_{k=1}^{n}a_{k}\]

La notation G! n’est pas standard (vous ne la trouverez sans doute pas ailleurs que dans cette note). Elle est cohérente en raison de l’hypothèse de commutativité : peu importe l’ordre dans lequel les éléments de G sont énumérés. Signalons aussi que c’est l’associativité du produit dans G qui, fondamentalement, permet d’utiliser la notation \prod. En effet, sans associativité, l’écriture {\displaystyle \prod_{k=1}^{n}a_{k}} n’aurait aucun sens, puisque différents parenthésages pourraient a priori conduire à différents résultats.

warning-math-os

Considérons par exemple le groupe \mathbb{U}_{n} des racines n-èmes de l’unité.

Proposition 1

Pour tout n\in\mathbb{N}^{\star} :

    \[\left[\mathbb{U}_{n}\right]!=\left(-1\right)^{n-1}\]

En effet, par définition :

    \[\left[\mathbb{U}_{n}\right]!=\prod_{k=0}^{n-1}e^{2ik\pi/n}=\exp\left(\frac{2i\pi}{n}\sum_{k=0}^{n-1}k\right)\]


Or, il est bien connu que {\displaystyle \sum_{k=0}^{n-1}k=\frac{n\left(n-1\right)}{2}.} Par conséquent :

    \[\left[\mathbb{U}_{n}\right]!=\exp\left(i\pi\left(n-1\right)\right)\]

et donc, d’après la formule de Moivre :

    \[\left[\mathbb{U}_{n}\right]!=\left(e^{i\pi}\right)^{n-1}=\left(-1\right)^{n-1}\]

Plus généralement :

Proposition 1-bis

Soit G groupe cyclique de cardinal n et d’élément neutre e. Alors :

    \[G!=\left\{ \begin{array}{cc}e & \text{ si }n\text{ est impair}\\\\\epsilon & \text{sinon}\end{array}\right.\]


\epsilon désigne (dans le cas où n est pair) l’unique élément d’ordre 2 dans G.

Deux groupes cycliques de même cardinal étant isomorphes, on peut se contenter d’invoquer la proposition précédente, mais je trouve éclairant de procéder de manière “directe”.

Les solutions dans G de l’équation x^{2}=e sont, d’une part l’élément neutre et, d’autre part, les éventuels éléments d’ordre 2. Or, dans un groupe fini de cardinal n, l’ordre de tout élément divise n et, si de plus le groupe est cyclique, alors pour tout diviseur d de n, les éléments d’ordre d sont les générateurs de l’unique sous-groupe de cardinal d (et ces éléments sont au nombre de \varphi\left(d\right)\varphi est l’indicatrice d’Euler). En particulier, on voit que :

  • G ne possède aucun élément d’ordre 2 si n est impair          [ cas 1 ]
  • G possède un unique élément d’ordre 2 sinon                      [ cas 2 ]

Considérons maintenant le produit qui définit G! et plaçons-nous dans le premier cas. En mettant à part le neutre, il reste le produit d’un nombre pair d’éléments, que l’on peut apparier (chacun avec son inverse) : au final G!=e.

Dans le second cas, on isole e et \epsilon du produit et l’on procède de même (regroupement par paires de tous les éléments restants, chacun avec son inverse), ce qui conduit cette fois à G!=\epsilon.

Question

Que reste-t-il de ce résultat pour des groupes abéliens finis plus généraux (c’est-à-dire : non cycliques) ?

Proposition 2

Pour tout groupe abélien fini G d’élément neutre e :

    \[\left[G!\right]^{2}=e\]

En effet, l’application G\rightarrow G,\thinspace x\mapsto x^{-1} est une bijection (qui coïncide avec sa réciproque). Par conséquent :

    \[\left[G!\right]^{2}=\left(\prod_{a\in G}a\right)^{2}=\left(\prod_{a\in G}a\right)\left(\prod_{a\in G}a^{-1}\right)=\prod_{a\in G}\left(aa^{-1}\right)=e\]


Ce dernier résultat est présenté ici pour son intérêt propre : dans tout groupe abélien fini, le produit des éléments est soit neutre soit d’ordre 2.

Cela dit, nous n’en aurons pas besoin dans la suite puisque le groupe \mathbb{F}_{p}^{\star} que nous allons utiliser est cyclique (et la proposition 1Bis s’appliquera).

3 – Théorème de Wilson

Supposons p premier, p\geqslant3, et appliquons au groupe \mathbb{F}_{p}^{\star} la méthode suivie pour la proposition 1Bis (à ceci près qu’il ne va pas être nécessaire de savoir au préalable que ce groupe est cyclique).

Les solutions dans le corps \mathbb{F}_{p} de l’équation x^{2}=\overline{1} sont \overline{1} et \overline{p-1}. Ces deux classes (qui n’en feraient qu’une pour p=2 …) sont donc les deux seuls éléments de \mathbb{F}_{p}^{\star} qui coïncident avec leur inverse. Les p-3 autres éléments vont donc pouvoir être appariés, chacun avec son inverse (noter que p-3 est pair) ce qui donne :

    \[\overline{\left(p-1\right)!}=\prod_{k=1}^{p-1}\overline{k}=\overline{1}\times\overline{p-1}\times\prod_{k=2}^{p-2}\overline{k}=\overline{p-1}=-\overline{1}\]


et donc :

    \[1+\left(p-1\right)!\equiv0\pmod{p}\qquad\left(\clubsuit\right)\]


Bien entendu, cette relation vaut aussi pour p=2.

Le théorème de Wilson est démontré.

Remarque

La réciproque du théorème de Wilson est vraie.

En effet, supposons qu’un entier p\geqslant2 vérifie \left(\clubsuit\right) et imaginons un instant que p ne soit pas premier. Alors il existerait un entier q tel que 1<q<p et q\mid p. De 1<q<p, on déduit que q\mid\left(p-1\right)! et de q\mid p on déduit que q\mid1+\left(p-1\right)! et donc, par différence, q\mid1 ce qui est absurde.

Ainsi, la congruence \left(\clubsuit\right) caractérise les nombres premiers. Bien entendu, ceci constitue un piètre test de primalité, car pour p assez grand, il faudrait calculer la factorielle de p-1, qui est un entier de taille colossale !

4 – Petit théorème de Fermat

Théorème

Si p\in\mathbb{P}, alors pour tout n\in\mathbb{N} :

    \[n^{p}\equiv n\pmod{p}\]

Ce résultat se démontre classiquement par récurrence (sur n bien sûr). La preuve repose de façon cruciale sur le fait que le coefficient binomial \binom{p}{k} est multiple de p, pour tout k tel que 1\leqslant k\leqslant p-1.

Si cette preuve vous intéresse, je vous invite à la lire en annexe.

Voici l’essence de notre démonstration :

Si G est un groupe abélien fini de cardinal q, alors :

  • en notant G=\left\{ a_{1},\cdots,a_{q}\right\}
  • et en choisissant x\in G (de sorte que x=a_{i} pour un certain i\in\left\{ 1,\cdots,q\right\} )

l’application G\rightarrow G,\thinspace g\mapsto xg est une bijection (dont la réciproque est G\rightarrow G,g\mapsto x^{-1}g). Par conséquent :

    \[ G!=\prod_{k=1}^{q}a_{k}=\prod_{k=1}^{q}\left(xa_{k}\right)=x^{q}\thinspace G!\]

et donc, après simplification par G! (tout élément est inversible dans un groupe) :

    \[ \boxed{x^{q}=e}\]

Remarque

Il découle du théorème de Lagrange (qui fait l’objet de cette vidéo) que dans tout groupe fini de cardinal q, (non nécessairement abélien), la puissance q-ème d’un quelconque élément est égale à l’élément neutre. L’intérêt de ce qui précède est d’en apporter une preuve simplifiée dans le cas particulier des groupes abéliens.

Appliquons ceci à G=\mathbb{F}_{p}^{\star} (ce qui impose q=p-1) et x=\overline{n} avec n\in\mathbb{N} non multiple de p (cette condition garantissant que \overline{n}\neq\overline{0}, c’est-à-dire \overline{n}\in\mathbb{F}_{p}^{\star}).

On obtient :

    \[\overline{n}^{p-1}=\overline{1}\]


ou encore :

    \[n^{p-1}\equiv1\pmod{p}\]


d’où, après multiplication par n :

    \[n^{p}\equiv n\pmod{p}\]


Par ailleurs, cette dernière relation est évidemment vraie si n est multiple de p. Elle est donc vraie pour tout n\in\mathbb{N} et le petit théorème de Fermat est démontré.

5 – Est-ce que 1 est un carré modulo p ?

Donnons-nous un nombre premier p et cherchons à quelle condition l’entier -1 est un carré modulo p, c’est-à-dire à quelle condition (sur p) il existe un entier k\in\left\{ 1,\cdots,p-1\right\} tel que :

    \[k^{2}\equiv-1\pmod{p}\]


Commençons par tâter le terrain en examinant de petites valeurs de p :

Lorsqu’une case de ce tableau est remplie, alors elle indique l’une des deux racines carrées de -1 modulo le nombre premier correspondant. Ainsi :

    \[12^{2}=144\equiv-1\pmod{29}\]


Et lorsqu’une case est vide, alors -1 n’est pas un carré modulo p. Par exemple, -1 n’est pas un carré modulo p=7, les seuls carrés non nuls étant \left(\pm1\right)^{2}=1, \left(\pm2\right)^{2}=4, \left(\pm3\right)^{2}=9\equiv2.

Conjecture

Il semblerait que, outre p=2, les seuls nombres premiers p pour lesquels -1 est un carré soient ceux congrus à 1 modulo 4.

C’est ce que nous allons maintenant établir.

→ Dans un sens …

Si -1 est un carré modulo p (avec p\in\mathbb{P}-\left\{ 2\right\} ), c’est qu’il existe a\in\left\{ 1,\cdots,p-1\right\} vérifiant :

    \[a^{2}\equiv-1\pmod{p}\]


Il s’ensuit que \overline{a} est un élément d’ordre 4 dans le groupe \mathbb{F}_{p}^{\star}, ce qui impose : 4\mid p-1.

Autrement dit : p\equiv1\pmod{4}.

← Dans l’autre sens …

Supposons que p\equiv1\pmod{4}.

On va considérer le produit des éléments de \mathbb{F}_{p}^{\star} et regrouper chaque facteur avec son opposé :

    \[\prod_{k=1}^{p-1}k=\prod_{k=1}^{\left(p-1\right)/2}k\left(p-k\right)\equiv\left(-1\right)^{\left(p-1\right)/2}\prod_{k=1}^{\left(p-1\right)/2}k^{2}=\left(-1\right)^{\left(p-1\right)/2}\left[\left(\frac{p-1}{2}\right)!\right]^{2}\]


Comme \frac{p-1}{2} est un entier pair, il vient :

    \[\left(p-1\right)!\equiv\left[\left(\frac{p-1}{2}\right)!\right]^{2}\]


et donc, d’après le théorème de Wilson (cf. section 3) :

    \[-1\equiv\left[\left(\frac{p-1}{2}\right)!\right]^{2}\]


ce qui prouve que -1 est un carré modulo p.

6 – En guise de conclusion

Nous avons regroupé trois propriétés d’arithmétique modulaire :

le théorème de Wilson
le petit théorème de Fermat
un cas particulier du critère d’Euler

[1]
[2]
[3]

Le trait d’union entre elles consiste en la possibilité d’être établies en manipulant, de différentes façons, le produit des éléments du groupe \mathbb{F}_{p}^{\star}.

  • Pour [ 1 ], on regroupe chaque facteur (autre que \overline{1} et \overline{p-1}) avec son inverse (dans le groupe \mathbb{F}_{p}^{\star})
  • Pour [ 2 ], on multiplie chaque facteur par un même élément de \mathbb{F}_{p}^{\star} (ce qui n’altère pas le produit)
  • Pour [ 3 ], on regroupe chaque facteur avec son opposé (dans l’anneau \mathbb{Z}/p\mathbb{Z})

Annexe – le petit théorème de Fermat, par récurrence

On fixe un nombre premier p et l’on prouve, par récurrence, que pour tout n\in\mathbb{N} :

    \[ n^{p}\equiv n\pmod{p}\]

Cette assertion est à l’évidence vraie pour n=0.

Supposons-la vraie pour un certain n\in\mathbb{N}; alors d’après la formule du binôme :

    \[ \left(n+1\right)^{p}=\sum_{k=0}^{p}\binom{p}{k}n^{k}=n^{p}+1+\sum_{k=1}^{p-1}\binom{p}{k}n^{k}\]

L’hypothèse de récurrence nous montre donc que :

    \[ \left(n+1\right)^{p}\equiv n+1+\sum_{k=1}^{p-1}\binom{p}{k}n^{k}\pmod{p}\]

et il suffira, pour conclure, de s’assurer que :

    \[ \sum_{k=1}^{p-1}\binom{p}{k}n^{k}\equiv0\pmod{p}\]

Pour qu’une somme d’entiers soit multiple de p, il n’est certes pas nécessaire que chaque terme soit multiple de p, mais c’est évidemment suffisant ! Or justement :

Lemme

Pour tout entier k tel que 1\leqslant k\leqslant p-1 :

    \[ p\mid\binom{p}{k}\]

On commence par appliquer la formule du pion (voir cet article) :

    \[k\binom{p}{k}=p\binom{p-1}{k-1}\]

et comme k et p sont premiers entre eux (vu que p est premier et que k n’est pas multiple de p), le théorème de Gauss donne la conclusion.


Merci de me laisser un commentaire si cet article vous a plu ou d’utiliser le formulaire de contact si vous souhaitez poser une question.

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu