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

Théorème 1 (Wilson)

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

Théorème 2 (Fermat)

    \[\forall n\in\mathbb{N},n^{p}\equiv n\pmod{p}\]

Théorème 3 (Euler)

    \[\left\exists k\in\left\llbracket 0,p-1\right\rrbracket ;\thinspace-1\right)\equiv k^{2}\pmod{p}\Leftrightarrow\left(p=2\text{ ou }p\equiv1\pmod{4}\right)\]

Ce dernier énoncé est un cas particulier du critère d’Euler.

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

Section 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 relation de 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\llbracket 0,n-1\right\rrbracket ^{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}).

Section 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 ce groupe.

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

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

ATTENTION …

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 {\displaystyle \prod}. En effet, sans associativité, l’écriture {\displaystyle \prod_{k=1}^{n}a_{k}} n’aurait aucun sens, puisque différents parenthésages pourraient conduire – a priori – à des produits différents.

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. De plus, si 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). On voit en particulier que :

  • Cas 1 – Si n est impair, alors G ne possède aucun élément d’ordre 2
  • Cas 2 – Si n est pair, alors G possède un unique élément d’ordre 2

Considérons maintenant le produit qui définit G! et plaçons-nous, tour à tour, dans chacun de ces deux cas.

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) et au final :

    \[\fcolorbox{black}{myBlue}{$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 à :

    \[\fcolorbox{black}{myBlue}{$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) ?

La proposition ci-dessous apporte une réponse …

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 involution. 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).

Section 3 – Théorème de Wilson

Supposons p premier, p\geqslant3.

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 :

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

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 !

Section 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 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\llbracket 1,q\right\rrbracket )

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 étant 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 d’évidence 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é.

Section 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\llbracket 1,p-1\right\rrbracket 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 la seconde ligne de ce tableau est remplie, elle indique l’une des deux racines carrées de -1 modulo p. Par exemple :

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

Et lorsque la 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\llbracket 1,p-1\right\rrbracket 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é :

    \begin{equation*}\begin{split}\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}\end{split}\end{equation*}

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.

Section 6 – En guise de conclusion

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

[1] – le théorème de Wilson

[2] – le petit théorème de Fermat

[3] – un cas particulier du critère d’Euler

  • 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 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 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}\]

Comme p est premier et vu que k n’est pas multiple de p, alors les entiers k et p sont premiers entre eux. Le théorème de Gauss donne la conclusion.


Vos questions ou remarques sont les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire