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\equiv k^{2}\pmod{p}\right)\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 $\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 $\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.$

où $\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)$ où $\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$

De plus, si $\text{card}(G)$ est impair, alors $G!=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$

Et dans le cas où le cardinal de $G$ est impair, vu qu’il n’existe aucun élément d’ordre 2 (d’après le théorème de Lagrange), on voit que $G!=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é modulo $p$ 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