Le PGCD gaussien et l'algorithme de Cornacchia

Le théorème de Noël garantit l’existence de deux carrés sans jamais les produire. C’est la faiblesse ordinaire des démonstrations d’existence, et la sortie du devoir promet trois compléments pour la réparer : la méthode du PGCD dans $\mathbb{Z}[i]$, sa traduction en arithmétique ordinaire, et le compte des points du réseau. Les voici. On note $\mathbb{Z}[i]$ l’ensemble des $z = a+ib$ avec $a \in \mathbb{Z}$ et $b \in \mathbb{Z}$, et $\mathrm{N}(z) = z\overline{z} = a^2+b^2$ la norme de $z$, à valeurs dans $\mathbb{N}$ et multiplicative.

1. L’algorithme d’Euclide dans $\mathbb{Z}[i]$

Tout part du théorème que le devoir établit dans sa partie II, et que l’on prend ici pour acquis sans le redémontrer.

Théorème (division euclidienne dans $\mathbb{Z}[i]$). Pour tous $z \in \mathbb{Z}[i]$ et $w \in \mathbb{Z}[i]$ avec $w \neq 0$, il existe $q \in \mathbb{Z}[i]$ et $r \in \mathbb{Z}[i]$ tels que $z = qw + r$ et $\mathrm{N}(r) < \mathrm{N}(w)$. Le couple $(q\,;r)$ n’est pas nécessairement unique.

En pratique, on calcule le quotient $\dfrac{z}{w}$ sous forme algébrique, on arrondit séparément ses deux coordonnées au nœud le plus proche du réseau, et l’on pose $r = z - qw$.

Cette division suffit à faire tourner l’algorithme d’Euclide, exactement comme dans $\mathbb{Z}$, et deux remarques valident le procédé. Il s’arrête, car les normes des restes successifs forment une suite strictement décroissante d’entiers naturels. Et à chaque étape l’égalité $z = qw+r$ montre que les diviseurs communs de $z$ et $w$ sont exactement ceux de $w$ et $r$ : cet ensemble ne change jamais. Le dernier reste non nul divise donc les deux nombres de départ et est divisible par tous leurs diviseurs communs : c’est un PGCD, défini à multiplication près par $1$, $-1$, $i$ ou $-i$.

Un exemple complet. Prenons $p = 89$, qui est premier et vaut $4 \times 22 + 1$, et l’entier $m = 34$, qui vérifie $34^2 + 1 = 1157 = 13 \times 89$. Calculons le PGCD de $89$ et de $34+i$ dans $\mathbb{Z}[i]$.

Première division. $\dfrac{89}{34+i} = \dfrac{89(34-i)}{1157} = \dfrac{3026 - 89i}{1157} \approx 2{,}615 - 0{,}077\,i$. Le nœud le plus proche est $q_1 = 3$, d’où

$$r_1 = 89 - 3(34+i) = -13 - 3i, \qquad \mathrm{N}(r_1) = 178 < 1157 .$$

Deuxième division. $\dfrac{34+i}{-13-3i} = \dfrac{-445+89i}{178} = -2{,}5 + 0{,}5\,i$. Ici le nœud le plus proche n’est pas unique, et c’est exactement l’ambiguïté que le résultat R3 du devoir annonce en refusant l’unicité du couple $(q\,;r)$. Choisissons $q_2 = -2$ :

$$r_2 = (34+i) - (-2)(-13-3i) = 8 - 5i, \qquad \mathrm{N}(r_2) = 89 < 178 .$$

Troisième division. $\dfrac{-13-3i}{8-5i} = -1-i$, qui appartient à $\mathbb{Z}[i]$ : le reste est nul.

Le dernier reste non nul est $8-5i$, de norme $89$. Et l’on lit la conclusion sur ses deux coordonnées :

$$89 = 8^2 + 5^2 .$$

Voilà la méthode, et elle n’a rien d’un hasard. Notons $d$ le PGCD de $p$ et de $m+i$. Il divise $p$, donc $\mathrm{N}(d)$ divise $\mathrm{N}(p) = p^2$ : cette norme vaut $1$, $p$ ou $p^2$. Elle ne vaut pas $1$ : sinon la relation de Bézout de la partie III du devoir fournirait $u$ et $v$ dans $\mathbb{Z}[i]$ tels que $pu + (m+i)v = 1$, et en multipliant par $m-i$ il viendrait $p\,u(m-i) + \left(m^2+1\right)v = m-i$, donc $p$ diviserait $m-i$, ce qui est exclu par la partie imaginaire. Elle ne vaut pas non plus $p^2$ : $d$ serait alors associé à $p$, qui ne divise pas $m+i$ pour la même raison. Donc $\mathrm{N}(d) = p$, et les deux coordonnées de $d$ sont les deux carrés cherchés.

Un autre choix de nœud à la deuxième division aurait donné $-8+5i$, ou $5+8i$ : le même nombre à un inversible près, donc la même paire de carrés.

2. Cornacchia, la même chose sans nombres complexes

En $1908$, Giuseppe Cornacchia publie une version de ce calcul qui ne mentionne aucun nombre complexe et qui tient en trois lignes.

L’algorithme. Soit $p$ un nombre premier tel que $p \equiv 1 \ [4]$, et soit $m$ un entier tel que $0 < m < p$ et $p$ divise $m^2+1$ ; c’est l’entier fourni par le résultat R4 du devoir.

1. Lancer l’algorithme d’Euclide ordinaire sur le couple $(p\,;m)$.
2. S’arrêter au premier reste strictement inférieur à $\sqrt{p}$ ; on le note $x$.
3. Poser $y = \sqrt{p - x^2}$. Alors $p = x^2 + y^2$.

L’exemple. Reprenons $p = 89$ et $m = 34$. On a $\sqrt{89} \approx 9{,}43$.

$$89 = 2 \times 34 + 21, \qquad 34 = 1 \times 21 + 13, \qquad 21 = 1 \times 13 + 8 .$$

Les restes successifs sont $21$, puis $13$, puis $8$. Le premier qui passe sous $9{,}43$ est $8$ : donc $x = 8$, puis $y = \sqrt{89-64} = 5$, et $89 = 64+25$. Trois divisions d’entiers, et le calcul est fini.

Pourquoi cela marche. L’algorithme de Cornacchia est le PGCD gaussien de $p$ et de $m+i$, regardé à travers les seules parties réelles. Comparez les deux calculs menés plus haut : les restes gaussiens étaient $89$, $34+i$, $-13-3i$, $8-5i$, dont les parties réelles valent, au signe près, $89$, $34$, $13$, $8$ ; la suite des restes d’Euclide ordinaire est $89$, $34$, $21$, $13$, $8$. La première est une sous-suite de la seconde, parce que l’arrondi au nœud le plus proche saute parfois une étape que l’arrondi par défaut, celui de la division dans $\mathbb{N}$, effectue en deux fois.

Le seuil $\sqrt{p}$, lui, sert de détecteur : le PGCD gaussien cherché a pour norme $p$, donc ses deux coordonnées sont de valeur absolue strictement inférieure à $\sqrt{p}$, tandis que les restes qui le précèdent restent au-dessus. Le premier reste ordinaire à passer sous $\sqrt{p}$ est donc exactement la partie réelle du PGCD, et le calcul de $y$ ne fait que retrouver l’autre coordonnée. La vérification complète de cette correspondance est un exercice classique, technique mais sans idée nouvelle, qui repose sur la théorie des fractions continues à quotients arrondis.

Reste le vrai travail, et il est en amont : trouver $m$. C’est le résultat admis du devoir, celui qui viendra du théorème de Wilson au chapitre A3. Une fois $m$ connu, Cornacchia rend les deux carrés en quelques dizaines de divisions, même pour un nombre premier à trente chiffres. Le contraste avec le tâtonnement est total.

3. Compter les points du réseau : le théorème de Jacobi

Dernière dette. Combien de points à coordonnées entières porte le cercle de centre l’origine et de rayon $\sqrt{n}$ ? Autrement dit, combien de couples $(a\,;b)$ d’entiers relatifs, l’ordre comptant, vérifient $a^2+b^2 = n$ ? Notons $r_2(n)$ ce nombre. La réponse porte un nom.

Théorème (Jacobi, $1829$). Pour tout $n \in \mathbb{N}^{*}$,

$$r_2(n) = 4\left(d_1(n) - d_3(n)\right),$$

où $d_1(n)$ est le nombre de diviseurs positifs de $n$ congrus à $1$ modulo $4$, et $d_3(n)$ le nombre de ceux qui sont congrus à $3$ modulo $4$.

L’idée de la démonstration. Un point du réseau sur le cercle, c’est exactement un $z \in \mathbb{Z}[i]$ de norme $n$. On les compte par leur factorisation, en admettant l’unicité de la décomposition en irréductibles de $\mathbb{Z}[i]$, le résultat R5 du devoir.

Il faut d’abord connaître les irréductibles de $\mathbb{Z}[i]$, et le devoir en donne la clé : $2$ se casse en $(1+i)(1-i)$, deux facteurs associés ; chaque premier $p \equiv 1 \ [4]$ se casse en $\pi\overline{\pi}$, avec $\pi$ et $\overline{\pi}$ irréductibles non associés, chacun de norme $p$ ; chaque premier $q \equiv 3 \ [4]$ reste irréductible, de norme $q^2$.

Écrivons alors $n = 2^{\,c} \prod p^{\,a_p} \prod q^{\,b_q}$, où les $p$ parcourent les premiers congrus à $1$ et les $q$ ceux congrus à $3$. Un élément $z$ de norme $n$ s’écrit nécessairement

$$z = \varepsilon \, (1+i)^{\,c} \prod \pi^{\,j_p}\,\overline{\pi}^{\,a_p - j_p} \prod q^{\,b_q/2},$$

et le décompte des choix se fait terme à terme. L’inversible $\varepsilon$ offre $4$ possibilités. Chaque premier congru à $1$ offre $a_p+1$ façons de répartir ses facteurs entre $\pi$ et $\overline{\pi}$, l’entier $j_p$ allant de $0$ à $a_p$. Chaque premier congru à $3$ n’offre aucun choix, et impose que $b_q$ soit pair, faute de quoi aucun $z$ n’existe. Le facteur $2$ n’offre aucun choix non plus. Au total :

$$r_2(n) = 4 \prod_{p\,\equiv\,1\,[4]} \left(a_p+1\right) \quad \text{si tous les } b_q \text{ sont pairs}, \qquad r_2(n) = 0 \text{ sinon}.$$

Il reste à reconnaître là le membre de droite du théorème. Posons $\chi(d) = 1$ si $d \equiv 1 \ [4]$, $\chi(d) = -1$ si $d \equiv 3 \ [4]$, et $\chi(d) = 0$ si $d$ est pair. Alors $d_1(n) - d_3(n) = \sum_{d \mid n} \chi(d)$, et comme $\chi$ est complètement multiplicative, cette somme est une fonction multiplicative de $n$ : il suffit de l’évaluer sur les puissances de nombres premiers. Sur $2^{\,c}$ elle vaut $1$, seul le diviseur $1$ étant impair. Sur $p^{\,a}$ avec $p \equiv 1$, tous les diviseurs sont congrus à $1$ et elle vaut $a+1$. Sur $q^{\,b}$ avec $q \equiv 3$, les diviseurs alternent entre les deux classes et elle vaut $1$ si $b$ est pair, $0$ sinon. Les deux produits coïncident terme à terme. $\square$

Quatre contrôles, faits à la main.

$n$	décomposition	$d_1(n) - d_3(n)$	$r_2(n)$
$72$	$2^3 \times 3^2$	$2 - 1 = 1$	$4$
$169$	$13^2$	$3 - 0 = 3$	$12$
$77$	$7 \times 11$	$2 - 2 = 0$	$0$
$85$	$5 \times 17$	$4 - 0 = 4$	$16$

Et les points eux-mêmes, pour que le compte se vérifie à l’œil : sur le cercle de rayon $\sqrt{72}$, les quatre points $(\pm 6\,;\pm 6)$ ; sur celui de rayon $13$, les douze points $(0\,;\pm 13)$, $(\pm 13\,;0)$, $(\pm 5\,;\pm 12)$ et $(\pm 12\,;\pm 5)$ ; sur celui de rayon $\sqrt{77}$, aucun ; sur celui de rayon $\sqrt{85}$, les seize points $(\pm 2\,;\pm 9)$, $(\pm 9\,;\pm 2)$, $(\pm 6\,;\pm 7)$ et $(\pm 7\,;\pm 6)$.

Le cas de $72$ mérite un regard : le facteur $3$ y est congru à $3$ modulo $4$, mais il y figure au carré, et le cercle porte quand même quatre points. Le cas de $77$ est l’inverse : deux facteurs congrus à $3$, chacun à l’exposant $1$, et le cercle est vide.

Ce n’est pas une coïncidence. La formule de Jacobi contient tout le critère : $r_2(n)$ est nul exactement lorsqu’un facteur premier congru à $3$ modulo $4$ apparaît à un exposant impair. Le théorème qui trie les entiers en deux familles n’est donc que le cas particulier « $r_2(n) = 0$ ou non » d’un énoncé qui, lui, sait compter.

Sources

• Devoir C1 n°1, Le théorème de Noël : partie II pour la division euclidienne prise ici pour acquise, résultat R5 pour l’unicité de la décomposition, questions Q15a et Q15c pour les deux promesses tenues sur cette page. Atelier C1, exercice $28$, pour la norme et les inversibles.
• Giuseppe Cornacchia, Su di un metodo per la risoluzione in numeri interi dell’equazione $\sum_{h=0}^{n} C_h x^{n-h} y^{h} = P$, Giornale di Matematiche di Battaglini, $1908$.
• Carl Gustav Jacob Jacobi établit la formule de $r_2$ dans les Fundamenta nova theoriae functionum ellipticarum, $1829$, par une voie entièrement différente, celle des fonctions thêta. La preuve esquissée ici, par $\mathbb{Z}[i]$, est celle qu’on donne aujourd’hui.
• Toutes les valeurs numériques de cette page ont été vérifiées à la main ; la décomposition de $89$ est en outre recalculée par le deuxième script de la page voisine.