Les racines carrées de $\overline{1}$ dans $\mathbb{Z}/n\mathbb{Z}$

La stratégie, et les outils. Un isomorphisme d'anneaux transporte toute équation polynomiale : $x$ est solution dans $\mathbb{Z}/n\mathbb{Z}$ si et seulement si chacune de ses composantes l'est dans son facteur, et le comptage devient un produit. Reste à compter dans un facteur $\mathbb{Z}/p^k\mathbb{Z}$ — c'est là que la parité de $p$ intervient. Outils : le théorème chinois et la valuation $p$-adique, c'est-à-dire l'exposant de $p$ dans une décomposition.

a) Dans $\mathbb{Z}/8\mathbb{Z}$. On teste les huit classes : $0^2=0$, $1^2=1$, $2^2=4$, $3^2=9\equiv 1$, $4^2=16\equiv 0$, $5^2=25\equiv 1$, $6^2=36\equiv 4$, $7^2=49\equiv 1$. D'où $$\left\{x\in \mathbb{Z}/8\mathbb{Z}:x^2=\overline{1}\right\}=\left\{\overline{1},\overline{3},\overline{5},\overline{7}\right\}:\text{ quatre solutions.}$$ Commentaire. Le polynôme $X^2-1$, de degré $2$, possède quatre racines. Il n'y a pas d'erreur : le théorème « au plus $d$ racines » vaut sur un corps, et $\mathbb{Z}/8\mathbb{Z}$ n'en est pas un — il n'est même pas intègre. La factorisation $X^2-1=(X-1)(X+1)$ y admet des solutions parasites : pour $x=\overline{3}$, les deux facteurs $\overline{2}$ et $\overline{4}$ sont non nuls et leur produit est nul.

b) Dans $\mathbb{Z}/p^k\mathbb{Z}$, $p$ premier impair. L'équation s'écrit $p^k\mid (x-1)(x+1)$.

Le point délicat. $p$ ne peut pas diviser les deux facteurs : sinon il diviserait leur différence $2$, ce qui est exclu pour $p$ premier impair. Notons $v=v_p(x-1)$ et $w=v_p(x+1)$ : on vient de voir que $\min (v,w)=0$, et l'hypothèse donne $v+w\ge k$. Donc $v\ge k$ ou $w\ge k$, c'est-à-dire $$x\equiv 1\left[p^k\right]\text{ou}x\equiv -1\left[p^k\right].$$ Réciproquement ces deux classes conviennent, et elles sont distinctes : $\overline{1}=\overline{-1}$ exigerait $p^k\mid 2$, impossible. Exactement deux solutions.

c) Le comptage par le théorème chinois. Les $p_i^{{\alpha }_i}$ sont deux à deux premiers entre eux, d'où un isomorphisme d'anneaux $$\Psi :\mathbb{Z}/n\mathbb{Z}⟶\mathbb{Z}/p_1^{{\alpha }_1}\mathbb{Z}\times \cdots \times \mathbb{Z}/p_r^{{\alpha }_r}\mathbb{Z}.$$ Un isomorphisme d'anneaux respecte produits et unité, donc $$x^2=\overline{1}⟺\Psi (x{)}^2=\left(\overline{1},\dots ,\overline{1}\right)⟺\forall i,{\left(\Psi (x{)}_i\right)}^2=\overline{1}.$$ $\Psi$ étant bijective, les solutions sont en bijection avec les $r$-uplets de solutions composante par composante ; chaque composante offre deux choix indépendants (question b), d'où $$\#\left\{x\in \mathbb{Z}/n\mathbb{Z}:x^2=\overline{1}\right\}=2^r,$$ où $r=\omega (n)$ est le nombre de facteurs premiers distincts de $n$. Remarquable : ce nombre ne dépend pas des exposants ${\alpha }_i$.

d) Deux vérifications.

$n=15=3\times 5$, $r=2$ : on attend $4$ solutions. Les quatre combinaisons de signes donnent, par le chinois, $\overline{1}$ ; $\overline{14}$ ; la classe $\equiv 1[3]$ et $\equiv 4[5]$, soit $\overline{4}$ ; et $\overline{11}$. Contrôles : $4^2=16=15+1$ ✓ ; $11^2=121=8\times 15+1$ ✓ ; $14^2=196=13\times 15+1$ ✓.

$n=105=3\times 5\times 7$, $r=3$ : on attend $8$ solutions. En résolvant les huit systèmes de congruences : $\overline{1},\overline{29},\overline{34},\overline{41},\overline{64},\overline{71},\overline{76},\overline{104}$. Contrôles : $29^2=841=8\times 105+1$ ✓ ; $41^2=1681=16\times 105+1$ ✓ ; $64^2=4096=39\times 105+1$ ✓ ; $76^2=5776=55\times 105+1$ ✓. Les solutions vont par paires $\{x,105-x\}$ : c'est la stabilité de l'ensemble par $x\mapsto -x$.

e) Le cas pair. L'argument du b) échoue pour $p=2$, précisément parce que $2$ divise $x-1$ et $x+1$ lorsque $x$ est impair.

• $\alpha =1$ : dans $\mathbb{Z}/2\mathbb{Z}$, seule $\overline{1}$ convient — une solution.
• $\alpha =2$ : dans $\mathbb{Z}/4\mathbb{Z}$, $1^2=1$ et $3^2=9\equiv 1$ — deux solutions.
• $\alpha \ge 3$ : quatre solutions. En effet $x$ est nécessairement impair, et $2^{\alpha }\mid (x-1)(x+1)$ où les deux facteurs sont pairs et diffèrent de $2$, donc un seul est divisible par $4$ : $\min \left(v_2(x-1),v_2(x+1)\right)=1$, et la somme des deux valuations étant $\ge \alpha$, la plus grande vaut au moins $\alpha -1$, soit $x\equiv \pm 1\left[2^{\alpha -1}\right]$. Réciproquement, si $x=1+2^{\alpha -1}t$, alors $x^2=1+2^{\alpha }t+2^{2\alpha -2}{t}^2\equiv 1\left[2^{\alpha }\right]$ dès que $\alpha \ge 2$ ; idem pour $-1$. Les classes obtenues, $\overline{1}$, $\overline{2^{\alpha -1}-1}$, $\overline{2^{\alpha -1}+1}$ et $\overline{2^{\alpha }-1}$, sont deux à deux distinctes dès que $\alpha \ge 3$ ; pour $\alpha =3$ on retrouve $\left\{\overline{1},\overline{3},\overline{5},\overline{7}\right\}$, exactement le a).

Le compte général. Pour $n=2^{\alpha }m$ avec $m$ impair, le chinois donne $c(\alpha )\times 2^{\omega (m)}$ solutions, où $c(0)=c(1)=1$, $c(2)=2$ et $c(\alpha )=4$ pour $\alpha \ge 3$.

Ce que l'exercice installe. Un isomorphisme transporte une équation : au lieu de résoudre dans $\mathbb{Z}/n\mathbb{Z}$, on résout dans chaque facteur et l'on multiplie les comptes. C'est le mode d'emploi du théorème chinois, plus utile que la résolution d'un système de congruences. Et le contraste du a) : hors d'un corps, un polynôme de degré $2$ peut avoir quatre racines — c'est exactement ce dont le problème de la séance aura besoin, en sens inverse, pour exploiter le fait que ${\mathbb{F}}_p$, lui, est un corps.