Problèmes de Mathématiques - Entiers de Gauss

Ce document présente un ensemble de problèmes et leurs corrigés portant sur les entiers de Gauss, un anneau d’entiers complexes de la forme a + ib avec a et b entiers relatifs. Il s’agit d’un contrôle approfondi visant à tester les compétences en algèbre, notamment la théorie des anneaux, la divisibilité, la division euclidienne, le calcul du pgcd, la factorisation, ainsi que la programmation algorithmique dans ce contexte.

Partie I. Divisibilité dans l’anneau ZZi

On demande ici de démontrer que ZZi est un anneau, d’étudier la divisibilité et la relation d’association dans cet anneau.

1. Montrer que (ZZi, +, ×) est un anneau et préciser la relation avec ZZ.

Pour montrer que ZZi est un anneau, on vérifie qu’il est stable par addition et multiplication, et qu’il contient l’élément neutre 1.

• 1 = 1 + 0i ∈ ZZi.
• Si z = a + ib et z' = c + id dans ZZi, alors z − z' = (a−c) + i(b−d) ∈ ZZi car a−c et b−d sont entiers.
• De même, zz' = (ac−bd) + i(ad+bc) ∈ ZZi car ac−bd et ad+bc sont entiers.

Conclusion : ZZi est un sous-anneau de (ℂ, +, ×). De plus, ZZ est un sous-anneau de ZZi puisque ZZ ⊂ ZZi (les entiers réels sont des entiers de Gauss avec partie imaginaire nulle).

Réponse : ZZi est un anneau, et ZZ est un sous-anneau de ZZi.

2. Montrer que les seuls éléments inversibles de ZZi sont 1, i, −1, −i.

Soit z = a + ib inversible dans ZZi. Il existe z' = c + id dans ZZi tel que zz' = 1.

On utilise la norme ϕ(z) = a² + b². On a :

ϕ(zz') = ϕ(z)ϕ(z') = ϕ(1) = 1

Or ϕ(z), ϕ(z') ∈ ℕ, donc ϕ(z) = ϕ(z') = 1.

Les seuls entiers a, b tels que a² + b² = 1 sont (±1, 0) ou (0, ±1), donc les seuls inversibles sont 1, i, −1, −i.

Réponse : Les seuls éléments inversibles de ZZi sont 1, i, −1, −i.

3. Relation de divisibilité et association dans ZZi.

(a) Montrer que pour z, z' ∈ ZZ, z | z' dans ZZ si et seulement si z divise z' dans ZZi.

Si z | z' dans ZZ, alors il existe q ∈ ZZ tel que z' = qz. Comme ZZ ⊂ ZZi, q ∈ ZZi, donc z divise z' dans ZZi.

Inversement, si z divise z' dans ZZi, alors il existe q ∈ ZZi tel que z' = qz. Si z ≠ 0, alors q = z'/z est un entier relatif (car z, z' ∈ ZZ), donc q ∈ ZZ. Ainsi la divisibilité dans ZZ coïncide avec celle dans ZZi.

Réponse : La divisibilité dans ZZi prolonge celle dans ZZ.

(b) Montrer que z k z' et z' k z (divisibilité mutuelle) implique qu’il existe u ∈ U = {1, i, −1, −i} tel que z' = uz.

Si z k z' et z' k z, alors il existe q, q' ∈ ZZi tels que z' = qz et z = q'z'. En composant, z = q'qz, donc (q'q − 1)z = 0.

Si z ≠ 0, alors q'q = 1, donc q et q' sont inversibles, donc dans U. Ainsi z et z' diffèrent par un élément inversible, ils sont associés.

Réponse : z et z' sont associés si et seulement si ils divisent mutuellement l’un l’autre.

(c) Montrer que ∼ est une relation d’équivalence sur ZZi, décrire la classe d’équivalence ez et son cardinal, et interpréter géométriquement.

La relation d’association est :

• Réflexive : z = 1 × z avec 1 ∈ U.
• Symétrique : si z' = uz, alors z = u⁻¹ z' avec u⁻¹ ∈ U.
• Transitive : si z' = uz et z'' = vz', alors z'' = (vu)z avec vu ∈ U.

Donc ∼ est une relation d’équivalence.

La classe ez = {z, iz, −z, −iz} a cardinal 4 sauf si z=0 où la classe est réduite à {0}.

Géométriquement, ez correspond aux quatre points du plan complexes obtenus par rotation de z de multiples de 90° autour de l’origine, formant les sommets d’un carré centré en 0.

Réponse : ∼ est une relation d’équivalence, chaque classe contient 4 éléments associés (sauf 0), formant un carré géométrique.

(d) Montrer que pour z ≠ 0, il existe un unique élément z+ dans ZZ+ i (a ≥ 1, b ≥ 0) associé à z.

On partitionne ZZi \ {0} en quatre ensembles : ZZ+ i , iZZ+ i , −ZZ+ i , −iZZ+ i . Chaque élément z non nul appartient à l’un de ces ensembles, et ses associés sont dans les trois autres.

Donc parmi les associés de z, un seul est dans ZZ+ i . On note cet élément z+.

Réponse : Chaque classe d’association contient un unique élément dans ZZ+ i, noté z+.

4. Étudier les ensembles de diviseurs et multiples dans ZZi.

(a) Montrer que zZZi ⊂ z'ZZi ⇔ z' k z ⇔ Di(z') ⊂ Di(z), et en déduire les égalités.

Si zZZi ⊂ z'ZZi, alors z ∈ z'ZZi donc z = z'q pour q ∈ ZZi, donc z' k z.

Si z' k z, alors tout multiple de z est multiple de z', donc zZZi ⊂ z'ZZi.

Un élément divise z' implique qu’il divise z, donc Di(z') ⊂ Di(z).

Les égalités zZZi = z'ZZi ⇔ z' ∼ z ⇔ Di(z) = Di(z').

Réponse : Ces inclusions et égalités caractérisent la divisibilité et l’association.

(b) Montrer que z divise ϕ(z) dans ZZi, et que z' k z ⇒ ϕ(z') | ϕ(z) dans ZZ.

On a ϕ(z) = zz = a² + b² ∈ ℕ. L’entier ϕ(z) est dans ZZ ⊂ ZZi.

On vérifie que z k ϕ(z) car ϕ(z) = z × z̄ avec z̄ = a − ib ∈ ZZi.

Si z' k z, alors z = q z' pour q ∈ ZZi, donc ϕ(z) = ϕ(q) ϕ(z'). Ainsi ϕ(z') | ϕ(z) dans ZZ.

Réponse : z divise ϕ(z), et la divisibilité dans ZZi entraîne une divisibilité des normes dans ZZ.

(c) Montrer que z' ∼ z ⇒ ϕ(z') = ϕ(z), mais que la réciproque est fausse.

Si z' ∼ z, alors z' = u z avec u ∈ U, et ϕ(u) = 1, donc ϕ(z') = ϕ(z).

Inversement, ϕ(z') = ϕ(z) ne garantit pas que z' et z soient associés, par exemple z = 3 + 4i et z' = 5 ont même norme 25, mais ne sont pas associés.

Réponse : L’association implique l’égalité des normes, mais pas l’inverse.

(d) Montrer que si z' k z et ϕ(z) = ϕ(z'), alors z' ∼ z.

Si z' k z, alors z = q z' avec q ∈ ZZi. En prenant les normes :

ϕ(z) = ϕ(q) ϕ(z'). Or ϕ(z) = ϕ(z'), donc ϕ(q) = 1, donc q ∈ U.

Donc z et z' sont associés.

Réponse : La divisibilité avec égalité des normes implique l’association.

(e) Déterminer Di(4 + 7i) ∩ ZZ+ i puis Di(4 + 7i).

On cherche les diviseurs ω = x + iy dans ZZ+ i tels que ω k z = 4 + 7i.

La norme ϕ(z) = 4² + 7² = 16 + 49 = 65 = 5 × 13.

Les normes possibles des diviseurs ω divisant z sont donc dans {1, 5, 13, 65}.

• Pour ϕ(ω) = 1 : ω = 1.
• Pour ϕ(ω) = 5 : solutions possibles ω = 1 + 2i ou 2 + i. Vérification montre que 2 + i divise z.
• Pour ϕ(ω) = 13 : solutions possibles ω = 2 + 3i ou 3 + 2i. Vérification montre que 3 + 2i divise z.
• Pour ϕ(ω) = 65 : ω ∼ z, donc z lui-même.

Donc Di(4 + 7i) ∩ ZZ+ i = {1, 2 + i, 3 + 2i, 4 + 7i}.

Les autres diviseurs sont les associés par multiplication par U :

Di(4 + 7i) = {±1, ±i, ±(2 + i), ±(−1 + 2i), ±(3 + 2i), ±(−2 + 3i), ±(4 + 7i), ±(−7 + 4i)}.

Réponse : Les diviseurs dans ZZ+ i sont {1, 2 + i, 3 + 2i, 4 + 7i}, et Di(4 + 7i) est l’ensemble de leurs associés.

Partie II. Division et pgcd dans ZZi

Cette partie traite de la division euclidienne, de l’algorithme d’Euclide et de la programmation associée.

1. Division euclidienne dans ZZi.

(a) Montrer qu’il existe de un à quatre éléments z ∈ ZZi tels que |z − ω| < 1, et au moins un tel que |z − ω| ≤ √2/2.

Pour ω = x + iy ∈ ℂ, on considère les entiers a, b proches de x, y. Les candidats sont :

z1 = [x] + i[y], z2 = ([x] + 1) + i[y], z3 = [x] + i([y] + 1), z4 = ([x] + 1) + i([y] + 1)

La distance |z − ω| < 1 implique que a est soit la partie entière de x, soit la partie entière + 1, de même pour b.

Selon la position de ω dans le carré formé par ces points, on a entre 1 et 4 solutions.

De plus, on montre que |z − ω| ≤ √2/2 en choisissant z par arrondi des parties réelles et imaginaires.

Réponse : Il existe entre 1 et 4 éléments z ∈ ZZi tels que |z − ω| < 1, et au moins un tel que |z − ω| ≤ √2/2.

(b) Montrer qu’il existe de un à quatre couples (q, r) ∈ ZZi² tels que z0 = qz + r avec ϕ(r) < ϕ(z).

Posons ω = z0/z. Trouver q ∈ ZZi tel que ϕ(z0 − qz) < ϕ(z) revient à trouver q ∈ ZZi avec |ω − q| < 1.

Comme il y a de 1 à 4 q possibles, on a de 1 à 4 divisions possibles.

Réponse : Il existe de un à quatre divisions euclidiennes possibles dans ZZi.

(c) Écrire toutes les divisions possibles de 1 + 11i par 3 + 4i et déterminer la meilleure division.

On calcule ω = (1 + 11i)/(3 + 4i) = (47 + 29i)/25 ≈ 1.88 + 1.16i.

Les candidats q sont 1 + i, 2 + i, 1 + 2i, 2 + 2i.

Calcul des restes r = z0 − qz et de ϕ(r) :

• q = 1 + i : r = 2(1 + 2i), ϕ(r) = 20
• q = 2 + i : r = −1, ϕ(r) = 1
• q = 1 + 2i : r = −1, ϕ(r) = 1
• q = 2 + 2i : r = 3(1 − i), ϕ(r) = 18

Les divisions valides sont celles avec ϕ(r) < ϕ(z) = 25, donc toutes sauf q = 1 + 2i (qui donne r = −1, ϕ(r) = 1, donc valide aussi).

La meilleure division est celle avec reste de norme minimale, ici r = −1 avec ϕ(r) = 1, soit q = 2 + i ou q = 1 + 2i.

Réponse : La meilleure division est z0 = (1 + 2i)z − 1.

(d) Vérifier que la division euclidienne classique dans ZZ est aussi une division dans ZZi.

Pour z0 ∈ ZZ et z ∈ ℕ*, la division euclidienne classique z0 = qz + r avec 0 ≤ r < z implique ϕ(r) < ϕ(z) car r et z sont entiers positifs.

Donc la division dans ZZ est aussi une division dans ZZi.

Réponse : La division euclidienne classique dans ZZ est une division dans ZZi.

(e) Écrire une procédure Maple div(z1, z2) renvoyant [q, r] avec q, r ∈ ZZi telle que z1 = q z2 + r et ϕ(r) < ϕ(z2).

On utilise la fonction round qui arrondit les parties réelles et imaginaires au plus proche entier :

div := proc(z1, z2)
  local q;
  q := round(z1 / z2);
  [q, z1 - q * z2]
end:

Exemple d’utilisation :

div(1 + 11*I, 3 + 4*I);
# Résultat : [2 + I, -1]

Réponse : La procédure div est donnée ci-dessus et fonctionne comme attendu.

2. Algorithme d’Euclide dans ZZi.

(a) Montrer que l’algorithme se termine après un nombre fini d’étapes.

La suite des normes des restes successifs ϕ(rk) est strictement décroissante dans ℕ.

Une suite strictement décroissante dans ℕ est finie, donc l’algorithme termine.

Réponse : L’algorithme d’Euclide dans ZZi termine en un nombre fini d’étapes.

(b) Prouver que Di(z) ∩ Di(z0) = Di(d) où d est le dernier reste non nul.

On utilise la propriété que Di(α) ∩ Di(β) = Di(β) ∩ Di(α − δβ) pour tout δ ∈ ZZi.

En appliquant cette propriété aux restes successifs, on obtient :

Di(z0) ∩ Di(z) = Di(r0) ∩ Di(r1) = Di(r1) ∩ Di(r2) = ... = Di(rn) = Di(d).

De plus, d est unique dans ZZ+ i tel que cette égalité soit vraie.

Réponse : L’intersection des diviseurs communs est l’ensemble des diviseurs de d.

(c) Montrer l’existence de coefficients de Bézout u, v ∈ ZZi tels que zu + z0v = d.

On construit par récurrence des suites (uk, vk) vérifiant zuk + z0vk = rk.

Initialisation :

• r0 = z0 = z0 × 1 + z × 0 ⇒ u0 = 0, v0 = 1
• r1 = z = z0 × 0 + z × 1 ⇒ u1 = 1, v1 = 0

Récurrence :

rk+1 = rk−1 − qk rk avec uk+1 = uk−1 − qk uk et vk+1 = vk−1 − qk vk.

Au rang n, on obtient (un, vn) tels que zun + z0vn = rn = d.

Réponse : Il existe u, v ∈ ZZi tels que zu + z0v = d.

(d) Montrer que d et ses associés sont les diviseurs communs de plus grand module.

Les diviseurs communs sont ceux de d, donc ont une norme divisant ϕ(d).

Les associés de d ont même norme ϕ(d), donc ont le plus grand module.

Réponse : Les diviseurs communs de plus grand module sont d et ses associés.

(e) Montrer que pour z, z0 ∈ ZZ, leur pgcd dans ZZ coïncide avec leur pgcd dans ZZi.

La division euclidienne classique dans ZZ est aussi une division dans ZZi.

Donc l’algorithme d’Euclide dans ZZ est un cas particulier de celui dans ZZi, et les pgcd coïncident.

Réponse : Le pgcd dans ZZ est le même que dans ZZi pour des entiers réels.

3. Programmation Maple associée.

(a) Procédure zpos renvoyant l’élément z+ associé à un z ∈ ZZi.

zpos := proc(z)
  local t;
  t := z;
  while t <> 0 and (Re(t) < 1 or Im(t) < 0) do
    t := I * t
  od;
  t;
end:

(b) Procédure itérative pgcd calculant le pgcd de deux entiers de Gauss.

pgcd := proc(z1, z2)
  local a, b, t;
  a := z1; b := z2;
  while b <> 0 do
    t := div(a, b);
    a := b;
    b := t[2];
  od;
  zpos(a);
end:

(c) Procédure récursive rpgcd calculant le pgcd.

rpgcd := proc(z1, z2)
  if z2 = 0 then
    zpos(z1)
  else
    rpgcd(z2, div(z1, z2)[2])
  fi;
end:

(d) Procédure itérative bezout calculant un couple de coefficients de Bézout.

bezout := proc(z1, z2)
  local a, b, u1, v1, u2, v2, u, v, t;
  a := z1; b := z2;
  u1 := 1; v1 := 0; u2 := 0; v2 := 1;
  while b <> 0 do
    t := div(a, b);
    a := b; b := t[2];
    u := u1 - t[1] * u2;
    v := v1 - t[1] * v2;
    u1 := u2; v1 := v2; u2 := u; v2 := v;
  od;
  t := a / zpos(a);
  [u1 / t, v1 / t];
end:

(e) Procédure récursive rbezout calculant un couple de coefficients de Bézout.

rbezout := proc(z1, z2)
  local d, t;
  if z2 = 0 then
    [zpos(z1) / z1, 0]
  else
    d := div(z1, z2);
    t := rbezout(z2, d[2]);
    [t[2], t[1] - d[1] * t[2]];
  fi;
end:

Partie IV. Entiers de Gauss premiers entre eux

On étudie ici la notion de primalité relative dans ZZi.

(a) Montrer que z ∧ z' = 1 ⇔ il existe (u, v) ∈ ZZi² tels que zu + z'v = 1 (identité de Bézout).

Si z ∧ z' = 1, alors d = 1, donc d divise 1, donc il existe u, v tels que zu + z'v = 1.

Inversement, si une telle identité existe, alors tout diviseur commun divise 1, donc est inversible, donc pgcd = 1.

Réponse : z et z' sont premiers entre eux si et seulement si une identité de Bézout existe.

(b) Montrer que si z divise z' z'' et que z ∧ z' = 1, alors z divise z''.

On utilise l’identité de Bézout : 1 = zu + z'v.

Multipliée par z'', on obtient z'' = z''zu + z''z'v = z(z''u) + z'(z''v).

Comme z divise z' z'', z divise le second terme, donc z divise z''.

Réponse : Si z est premier avec z', alors z divise z' z'' implique z divise z''.

(c) Montrer que si z ∧ z' = 1 et z ∧ z'' = 1, alors z ∧ (z' z'') = 1, et généraliser.

On applique la propriété précédente et la récurrence sur le produit.

Si z est premier avec chacun des facteurs, alors il est premier avec leur produit.

Réponse : La primalité relative se conserve par produit.

(d) Montrer que si z divise z'' et z' divise z'', et que z ∧ z' = 1, alors zz' divise z''.

On écrit z'' = q z et z'' = q' z'.

Comme z ∧ z' = 1, il existe u, v tels que zu + z'v = 1.

On a alors :

z'' = z'' (zu + z'v) = (q z)(u) + (q' z')(v) = (q u + q' v)(z z').

Donc zz' divise z''.

Réponse : Le produit de deux éléments premiers entre eux divise tout multiple commun.

Partie V. Entiers de Gauss irréductibles

On étudie ici la notion d’éléments irréductibles dans ZZi, leur caractérisation et leur factorisation.

(1) Propriétés des éléments irréductibles Pi.

(a) Montrer que z ∈ Pi ⇔ z+ ∈ Pi.

Les associés ont les mêmes diviseurs, donc la propriété d’être irréductible est stable par association.

Réponse : z est irréductible si et seulement si z+ l’est.

(b) Montrer que si p ∈ Pi ne divise pas z, alors p ∧ z = 1. En déduire que deux éléments distincts de P+ i sont premiers entre eux.

Si p ne divise pas z, alors tout diviseur commun d de p et z est inversible, donc p ∧ z = 1.

Si p ≠ q dans P+ i, alors p ne divise pas q, donc p ∧ q = 1.

Réponse : Les irréductibles distincts sont premiers entre eux.

(c) Montrer que si p ∈ Pi divise un produit z z0, alors p divise z ou p divise z0.

C’est la propriété de primalité des irréductibles dans ZZi.

Par récurrence, si p divise un produit de n facteurs, alors p divise au moins un facteur.

Réponse : Les irréductibles sont premiers.

(d) Montrer que si ϕ(z) est premier dans ℕ, alors z est irréductible.

Si z = ab, alors ϕ(z) = ϕ(a) ϕ(b). Comme ϕ(z) est premier, l’un des facteurs est 1, donc a ou b est inversible.

Réponse : Si la norme est un nombre premier, alors z est irréductible.

(2) Factorisation en produit de facteurs irréductibles normalisés.

(a) Montrer que tout z non nul et non inversible est divisible par au moins un élément p de P+ i.

Par récurrence sur ϕ(z), on trouve un facteur irréductible.

(b) Montrer que z s’écrit sous la forme z = u ∏ p_k^n_k avec u ∈ U, p_k ∈ P+ i, n_k ∈ ℕ*.

(c) Montrer que cette écriture est unique à l’ordre près.

Réponse : Tout élément non nul non inversible admet une décomposition unique en facteurs irréductibles normalisés.

(3) Irréductibilité des entiers naturels.

Proposition : Pour un nombre premier p, les conditions suivantes sont équivalentes :

• p n’est pas irréductible dans ZZi.
• p = a² + b² avec a, b ∈ ℕ*.
• p = 2 ou p ≡ 1 mod 4.

(a) Montrer que si p n’est pas irréductible, alors p = a² + b².

Si p n’est pas irréductible, il admet un diviseur non inversible dans ZZi, donc p = a² + b².

(b) Réciproquement, si p = a² + b², alors p n’est pas irréductible et sa factorisation est p = (a + ib)(a − ib).

La paire (a, b) est unique.

(c) Montrer que p = 2 n’est pas irréductible.

2 = (1 + i)(1 − i).

(d) Si p ≡ 1 mod 4, montrer que p n’est pas irréductible en utilisant le théorème de Wilson et une contradiction.

(e) Si p ≡ 3 mod 4, alors p est irréductible.

Réponse : Un entier premier p est irréductible dans ZZi si et seulement si p ≡ 3 mod 4.

(4) Caractérisation des éléments irréductibles normalisés de ZZi.

Proposition : Soit z = a + ib avec a, b ≥ 1. Alors z est irréductible si et seulement si ϕ(z) = a² + b² est un nombre premier égal à 2 ou congru à 1 modulo 4.

(a) Montrer qu’il existe un premier p tel que z divise p.

(b) Montrer que ϕ(z) = p.

Réponse : Les irréductibles normalisés sont caractérisés par la primalité de leur norme, qui est 2 ou congrue à 1 modulo 4.

En résumé, un élément z = a + ib de ZZ+ i est irréductible si et seulement si :

• b = 0 et a est premier avec a ≡ 3 mod 4, ou
• b ≥ 1 et a² + b² est un nombre premier différent de ceux congrus à 3 mod 4.

Méthode

Ce contrôle récompense une maîtrise rigoureuse des propriétés algébriques des entiers de Gauss, notamment :

• La compréhension précise de la structure d’anneau de ZZi et de la norme ϕ.
• La capacité à manipuler la divisibilité, les relations d’association et les classes d’équivalence.
• La maîtrise de la division euclidienne dans un anneau complexe, avec la recherche du quotient et du reste minimaux.
• La mise en œuvre de l’algorithme d’Euclide et la preuve de son terminaison.
• La construction des coefficients de Bézout et leur interprétation.
• La compréhension des propriétés des éléments premiers et irréductibles dans ZZi, ainsi que leur factorisation unique.
• La capacité à traduire ces notions en procédures algorithmiques efficaces (Maple).

Les erreurs pénalisées sont notamment :

• Confusion entre divisibilité dans ZZ et dans ZZi.
• Omissions dans la preuve de la terminaison de l’algorithme d’Euclide.
• Manque de rigueur dans la caractérisation des éléments inversibles et associés.
• Absence de justification des propriétés de la norme ϕ.
• Erreurs dans l’écriture ou l’interprétation des procédures Maple.
• Confusion entre irréductibilité et primalité dans ZZi.

Une rédaction claire, détaillée et ordonnée, avec des justifications complètes, est essentielle pour obtenir la meilleure note.