Travaux pratiques
Décomposition de p en somme de deux carrés
9. Soit c un élément de Z, tel que |c| < p/2 et que sa classe modulo p soit d’ordre
4 dans F ∗
p . On considère le morphisme d’anneaux f : Z[i] → F p défini par
f (1) = 1 et f (i) = c mod p. Vérifier que c’est bien un morphisme d’anneaux.
Montrer que le noyau de f est engendré (en tant que groupe abélien, donc en
tant qu’idéal) par p et i − c. En déduire, par l’algorithme d’Euclide du calcul
du pgcd dans Z[i], un générateur du noyau de f . Que prend-on comme entiers
a et b de façon à avoir p = a 2 + b 2 ?
10. En combinant l’ensemble de votre travail précédent, écrire une procédure
DeuxCarres, qui prend en entrée un nombre premier p et qui renvoie un couple
(a, b) tel que p = a 2 + b 2 si p est de la forme 4k + 1.
11. Question subsidiaire : proposer un algorithme, utilisant la procédure précédente, qui décompose en irréductibles un entier de Gauss quelconque donné.
Remarque. Pour achever la preuve de la proposition 1, il reste à démontrer que si
p ≡ −1 mod 4 alors p reste irréductible dans Z[i] (il ne s’écrit donc pas comme
somme de deux carrés). On démontre la contraposée : si p est réductible, il s’écrit
p = αβ (α ∈ U(Z[i]), β ∈ U(Z[i])), d’où N (p) = p 2 = N (α)N (β). Comme α
et β ne sont pas de norme 1, alors p = N (α). Écrivant α = a + ib, on obtient
p = a 2 + b 2 , d’où −b 2 ≡ a 2 mod p. On vérifie facilement que p ne divise pas b,
donc b est inversible modulo p. La congruence précédente montre alors que −1
est un carré modulo p. Comme les carrés (non nuls) modulo p forment un groupe
de cardinal (p − 1)/2 (c’est l’image de l’endomorphisme x → x 2 de F ∗
p ), on a
(−1)
p−1
2
= 1, ce qui est équivalent à p ≡ 1 mod 4.
Dans la même veine, on peut fournir une preuve, non constructive par contre
(à la différence de l’algorithme décrit plus haut), du fait que p ≡ 1 mod 4 s’écrit
comme somme de deux carrés : comme −1 est un carré modulo p (les carrés non
nuls modulo p sont exactement le noyau de l’endomorphisme x → x
p−1
2
de F ∗
p ),
disons −1 ≡ a 2 mod p, le nombre p divise a 2 + 1 = (a + i)(a − i), mais il ne divise
ni a + i, ni a − i. Il n’est donc pas premier dans Z[i], donc pas irréductible (c’est
une propriété des anneaux principaux). Or on vient de voir qu’il s’écrit alors sous
la forme p = a 2 + b 2 .
235
Décomposition de p en somme de deux carrés
9. Soit c un élément de Z, tel que |c| < p/2 et que sa classe modulo p soit d’ordre
4 dans F ∗
p . On considère le morphisme d’anneaux f : Z[i] → F p défini par
f (1) = 1 et f (i) = c mod p. Vérifier que c’est bien un morphisme d’anneaux.
Montrer que le noyau de f est engendré (en tant que groupe abélien, donc en
tant qu’idéal) par p et i − c. En déduire, par l’algorithme d’Euclide du calcul
du pgcd dans Z[i], un générateur du noyau de f . Que prend-on comme entiers
a et b de façon à avoir p = a 2 + b 2 ?
10. En combinant l’ensemble de votre travail précédent, écrire une procédure
DeuxCarres, qui prend en entrée un nombre premier p et qui renvoie un couple
(a, b) tel que p = a 2 + b 2 si p est de la forme 4k + 1.
11. Question subsidiaire : proposer un algorithme, utilisant la procédure précédente, qui décompose en irréductibles un entier de Gauss quelconque donné.
Remarque. Pour achever la preuve de la proposition 1, il reste à démontrer que si
p ≡ −1 mod 4 alors p reste irréductible dans Z[i] (il ne s’écrit donc pas comme
somme de deux carrés). On démontre la contraposée : si p est réductible, il s’écrit
p = αβ (α ∈ U(Z[i]), β ∈ U(Z[i])), d’où N (p) = p 2 = N (α)N (β). Comme α
et β ne sont pas de norme 1, alors p = N (α). Écrivant α = a + ib, on obtient
p = a 2 + b 2 , d’où −b 2 ≡ a 2 mod p. On vérifie facilement que p ne divise pas b,
donc b est inversible modulo p. La congruence précédente montre alors que −1
est un carré modulo p. Comme les carrés (non nuls) modulo p forment un groupe
de cardinal (p − 1)/2 (c’est l’image de l’endomorphisme x → x 2 de F ∗
p ), on a
(−1)
p−1
2
= 1, ce qui est équivalent à p ≡ 1 mod 4.
Dans la même veine, on peut fournir une preuve, non constructive par contre
(à la différence de l’algorithme décrit plus haut), du fait que p ≡ 1 mod 4 s’écrit
comme somme de deux carrés : comme −1 est un carré modulo p (les carrés non
nuls modulo p sont exactement le noyau de l’endomorphisme x → x
p−1
2
de F ∗
p ),
disons −1 ≡ a 2 mod p, le nombre p divise a 2 + 1 = (a + i)(a − i), mais il ne divise
ni a + i, ni a − i. Il n’est donc pas premier dans Z[i], donc pas irréductible (c’est
une propriété des anneaux principaux). Or on vient de voir qu’il s’écrit alors sous
la forme p = a 2 + b 2 .
235