Problèmes de Mathématiques - Entiers de Gauss

k=1

pnk

k , où :

– u est un élément de U = {1, i, −1, −i}. ; m est un élément de IN∗

– pour tout k de {1, . . . , m}, pk est dans ZZ+

[ S ]

i et nk dans IN∗.

(c) Montrer que l’écriture précédente de z est unique a l’ordre pres des facteurs.

[ S ]

3. Irréductibilité des éléments de IN∗.

Il est clair que si n ≥ 2 est un entier non premier, il n’est pas irréductible dans ZZi (ses

diviseurs dans IN étant aussi des diviseurs dans ZZi). Il reste donc à comprendre quand un

entier premier p est irréductible dans ZZi. Pour cela on va démontrer le résultat suivant :

Proposition

Soit p un nombre premier. Les conditions suivantes sont équivalentes :

– p n’est pas irréductible dans ZZi.

– Il existe a et b dans IN∗ tels que p = a2 + b2.

– p = 2, ou p est congru à 1 modulo 4.

(a) Montrer que si p n’est pas irréductible, alors ∃ (a, b) ∈ (IN∗)2, p = a2 + b2 (utiliser

un diviseur de p dans ZZi, non inversible et non associé à p.) [ S ]

c(cid:13)EduKlub S.A.

Page 4

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Énoncé

(b) Inversement, si p = a2 + b2 (avec a, b dans IN∗) montrer que p n’est pas irréductible

et écrire la factorisation de p en produit de facteurs irréductibles normalisés.

En déduire que la paire {a, b} de (IN∗)2 telle que p = a2 + b2 est unique. [ S ]

(c) Montrer que p = 2 n’est pas irréductible dans ZZi. [ S ]

(d) On rappelle le théorème de Wilson : p premier⇔ (p − 1)! ≡ −1 (p).

On suppose que p ≡ 1 (4). Il existe donc n dans IN∗ tel que p = 4n + 1.

Montrer que (p − 1)! ≡ (2n)!2. Ainsi, en posant m = (2n)!, on a m2 ≡ −1 (p).

Par l’absurde, on suppose que p est irréductible.

Montrer que p divise m + i ou m − i et aboutir à une contradiction.

Donc si p est premier et congru à 1 modulo 4, il n’est pas irréductible. [ S ]

(e) Montrer que si p ≡ 3 (4), alors p est irréductible (raisonner par l’absurde.)

Autrement si, si p n’est pas irréductible, il est égal a 2, ou congru a 1 modulo 4.

Ceci termine la démonstration de la proposition.

Le résultat de cette question peut être résumé ainsi : Un entier n ≥ 1 est irréductible

dans ZZi si et seulement si

(cid:26) n est premier

n ≡ 3 (4)

[ S ]

4. Eléments irréductibles normalisés de ZZi.

La question précédente indique quels éléments de IN∗ sont irréductibles.

Pour ce qui est des éléments de ZZ+

i , il reste à établir le résultat suivant :

Proposition

Soit z = a + ib, avec a ∈ IN∗ et b ∈ IN∗.

z est irréductible si et seulement si ϕ(z) = a2 + b2 est un entier premier.

De plus cet entier premier est égal a 2, ou est congru a 1 modulo 4.

On sait déja que si ϕ(z) est un entier premier, alors z est irréductible (cf III.1.d.)

La question III.3.e) a également montré qu’un entier premier congru à 3 modulo 4 (donc

qui n’est ni égal a 2 ni congru a 1 modulo 4) n’est jamais la somme de deux carrés.

Il reste donc a supposer que z = a + ib (a, b ≥ 1) est dans Pi et a montrer que ϕ(z) ∈ P.

(a) En considérant la décomposition de ϕ(z) en produits de facteurs premiers dans IN,

montrer qu’il existe un entier premier p tel que z k p.

[ S ]

(b) Avec les notations précédentes, montrer que ϕ(z) = p.

[ S ]

On a ainsi obtenu la caractérisation des éléments irréductibles normalisés de ZZi :

Proposition

Un élément de z = a + ib de ZZ+

– Ou bien : b = 0 et a est un nombre premier congru à 3 modulo 4.

– Ou bien : b ≥ 1 et a2 + b2 est un nombre premier non congru à 3 modulo 4.

i (a ≥ 1, b ≥ 0) est irréductible si et seulement si :

c(cid:13)EduKlub S.A.

Page 5

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

Corrigé du problème

Partie I. Divisibilité dans l’anneau ZZi.

1. Il suffit de vérifier que ZZi est un sous-anneau de ( lC, +×).

Tout d’abord ZZi contient 1 = 1 + 0i (le neutre multiplicatif de l’anneau lC.)

Si z = a + ib et z0 = c + id sont dans ZZi, il en est de même de :

– z − z0 = (a − c) + i(b − d)

– zz0 = (ac − bd) + i(ad + bc)

Conclusion : ZZi est un sous-anneau de ( lC, +, ×).

L’anneau (ZZ, +, ×) est bien sûr un sous-anneau de ZZi.

car ac − bd et ad + bc sont éléments de ZZ.

car a − c et b − d sont éléments de ZZ.

[ Q ]

2. Si z = a + ib est inversible dans ZZi, il existe z0 = c + id dans ZZi tel que zz0 = 1.

On a alors l’égalité 1 = ϕ(1) = ϕ(zz0) = ϕ(z)ϕ(z0).

ϕ(z) et ϕ(z0) étant des entiers naturels, cela implique ϕ(z) = 1.

Réciproquement, si ϕ(z) = a2 + b2 = 1, alors z = a − ib ∈ ZZi et zz = 1.

Conclusion : un élément z = a + ib de ZZi est inversible⇔ ϕ(z) = a2 + b2 = 1.

Il y a quatre solutions, qui sont les points a coordonnées entieres du cercle unité.

Les seuls éléments inversibles de ZZi sont donc 1, i, −1, −i.

(a) Soient z et z0 deux éléments de ZZ, donc deux éléments de ZZi.

[ Q ]

3.

– Supposons que z divise z0 dans ZZ, c’est-à-dire qu’il existe q dans ZZ tel que z0 = qz.

Alors z divise z0 dans ZZi car q est aussi un élément de ZZi.

– Réciproquement, supposons que z0 divise z dans ZZi.

Il existe donc un élément q de ZZi tel que z0 = qz.

Si z = 0, alors z0 = 0 et z divise z0 dans ZZ (z0 = mz pour tout m de ZZ.)

Si z 6= 0, alors q = z0

z est un entier relatif. Donc z divise z0 dans ZZ.

– Finalement, si z, z0 ∈ ZZ, z divise z0 dans ZZ ⇔ z divise z0 dans ZZi.

En ce sens, la relation de divisibilité dans ZZi prolonge celle de ZZ.

[ Q ]

(b) Soient z et z0 deux éléments de ZZi.

– S’il existe u dans U tel que z0 = uz, alors z = uz0 (et u ∈ U).

Autrement dit z k z0 et z0 k z.

– Réciproquement, supposons z k z0 et z0 k z.

Il existe donc deux éléments q, q0 de ZZi tels que z0 = qz et z = q0z0.

On en déduit z(qq0 − 1) = 0 donc z = 0 ou qq0 = 1.

Si z = 0, alors z0 = 0 et on peut bien écrire z0 = uz pour tout u de U.

Sinon qq0 = 1 montre que q et q0 sont deux éléments de U, inverses l’un de l’autre.

– Conclusion : pour tous z, z0 de ZZi, (z k z0 et z0 k z) ⇔ ∃ u ∈ U, z0 = uz.

[ Q ]

c(cid:13)EduKlub S.A.

Page 6

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

(c) – Pour tout z de ZZi, on a z = uz avec u = 1. La relation ∼ est donc réflexive.

– Si z0 = uz, avec u ∈ U, alors z = vz0, avec v = u ∈ U : ∼ est symétrique.

– Si

n z0 = uz

z00 = vz0 avec (u, v) ∈ U, alors z00 = wz, avec w = vu ∈ U : ∼ est transitive.

– Conclusion : la relation ∼ est d’équivalence sur ZZi.

Pour tout z de ZZi, ez = {z, iz, −z, −iz}. Si z = 0 alors ez = {0}, sinon Card ez = 4.

Interprétation géométrique : pour tout z de ZZi, les points-images des éléments de ez

sont les sommets du carré de centre 0 donc un sommet est m(z).

Remarque : les éléments de ez sont les solutions ω de ω4 = z4. La relation d’association

aurait d’ailleurs pu être définie par z ∼ z0 ⇔ z4 = z04, ce qui fait immédiatement

apparaˆıtre qu’il s’agit d’une relation d’équivalence.

[ Q ]

(d) Soit ϕ l’application de lC dans lC défini par ϕ(z) = iz.

Notons iZZ+

i

Notons −ZZ+

i

Notons −iZZ+

i

Il est clair que ZZi, iZZ+

l’ensemble des z = a + ib de ZZi tels que a ≤ 0 et b ≥ 1.

l’ensemble des z = a + ib de ZZi tels que a ≤ −1 et b ≤ 0.

l’ensemble des z = a + ib de ZZi tels que a ≥ 0 et b ≤ −1.

forment une partition de ZZi \ {0}.

i , −ZZ+

(

i

i , −iZZ+

iZZ+

−iZZ+

i = ϕ(ZZi)

i = ϕ(−ZZ+

i )

−ZZ+

ZZ+

i = ϕ(iZZ+

i )

i = ϕ(−iZZ+

i )

Il est tout aussi clair que

Tout élément z non nul de ZZi est dans l’un et l’un seulement de ces quatre ensembles.

Chacun des trois autres ensembles contient alors un et un seul de iz, −z, −iz.

L’un et l’un seulement des nombres complexes z, iz, −z, −iz est donc dans ZZ+

i .

Sur le schéma ci-dessous, on a fait figurer z = −4+3i et ses trois associés iz, −z, −iz.

De ces quatre complexes, seul −iz = 3 + 4i est dans ZZ+

i . On a donc ici z+ = −iz.

[ Q ]

c(cid:13)EduKlub S.A.

Page 7

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

4.

(a) – Supposons zZZi ⊂ z0ZZi. Alors z = z1 est dans zZZi donc dans z0ZZi.

Ainsi il existe q dans ZZi tel que z = z0q. Donc z0 k z.

– Si z0 k z, alors tout diviseur de z0 divise z. Donc Di(z0) ⊂ Di(z).

– Si Di(z0) ⊂ Di(z), alors z0 (qui est dans Di(z0)) est un diviseur de z.

Tout multiple de z est donc un multiple de z0. Ainsi zZZi ⊂ z0ZZi.

On en déduit : zZZi ⊂ z0ZZi ⇔ z0 k z ⇔ Di(z0) ⊂ Di(z).

Il en découle : zZZi = z0ZZi ⇔ Di(z) = Di(z0) ⇔ (z0 k z et z k z0) ⇔ z0 ∼ z.

[ Q ]

(b) On a ϕ(z) = zz, et z est un élément de ZZi. Donc z k ϕ(z).

[ Q ]

(c) Supposons z0 k z : il existe q dans ZZi tel que z = qz0.

On en déduit ϕ(z) = ϕ(q)ϕ(z0), avec ϕ(q) ∈ IN. Donc ϕ(z0) divise ϕ(z) dans ZZ.

La réciproque est fausse comme le montre l’exemple de z = 3 + 4i et de z0 = 5.

En effet l’unique q de lC tel que z = qz0 est q = 1

5 (3 + 4i) et n’est pas dans ZZi.

Donc z0 ne divise pas z dans ZZi. Pourtant on ϕ(z0) | ϕ(z) car ϕ(z) = ϕ(z0) = 25.

Si z0 = uz, avec u dans U, alors ϕ(z0) = ϕ(uz) = ϕ(u)ϕ(z) = ϕ(z).

Le même contre-exemple montre que ϕ(z0) = ϕ(z) n’implique pas z0 ∼ z.

[ Q ]

(d) Supposons z0 k z et ϕ(z) = ϕ(z0). Si z = 0, alors z0 = 0 et z, z0 sont associés.

Sinon ∃ q ∈ ZZi, q 6= 0, z = qz0. Alors ϕ(z) = ϕ(q)ϕ(z0) = ϕ(q)ϕ(z) ⇒ ϕ(q) = 1.

Cela prouve que q est élément de u, donc que z et z0 sont associés.

[ Q ]

(e) Posons z = 4 + 7i. On cherche un diviseur ω = x + iy dans ZZ+

i (x ∈ IN∗ et y ∈ IN.)

Nécessairement ϕ(ω) divise ϕ(z) = 42 + 72 = 65 = 5 · 13 donc ϕ(ω) ∈ {1, 5, 13, 65}.

– ϕ(ω) = x2 + y2 = 1 donne ω = 1 qui est bien un diviseur de z.

– ϕ(ω) = x2 + y2 = 5 donne ω = 1 + 2i ou ω = 2 + i.

ω = 1 + 2i ne convient pas car 4+7i

ω = 2 + i convient car 4+7i

5 (4 + 7i)(1 − 2i) = 1

1+2i = 1

5 (18 − i) /∈ ZZi.

5 (4 + 7i)(2 − i) = 3 + 2i donc z = (3 + 2i)ω.

2+i = 1

– ϕ(ω) = x2 + y2 = 13 donne ω = 2 + 3i ou ω = 3 + 2i.

ω = 2 + 3i ne convient pas car 4+7i

2+3i = 1

13 (4 + 7i)(2 − 3i) = 1

13(29 + 2i) /∈ ZZi.

ω = 3 + 2i convient car on sait que z = (3 + 2i)(2 + i).

– ϕ(ω) = 65 = ϕ(z) implique ω ∼ z donc ω = z car tous deux sont dans ZZ+

i .

Evidemment cette solution convient.

c(cid:13)EduKlub S.A.

Page 8

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

Les diviseurs de z = 4 + 7i qui sont dans ZZ+

Pour tout ω de ZZi, on a ω k z ⇔ ω+ k z (car ω k ω+ et ω+ k ω).

Les diviseurs de z dans ZZi sont donc les associés de ceux qui appartiennent à ZZ+

i .

On trouve donc :

i sont donc {1, 2 + i, 3 + 2i, 4 + 7i}.

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

−3 − 2i, 2 − 3i, 4 + 7i, −7 + 4i, −4 − 7i, 7 − 4i}

[ Q ]

Partie II. Division, pgcd et ppcm dans ZZi.

1.

(a) Posons ω = x + iy et z = a + ib (avec x, y dans IR et a, b dans ZZ).

On sait que pour tout nombre complexe Z, on a |Re (Z)| ≤ |Z| et |Im (Z)| ≤ |Z|.

Donc si |ω − z| < 1, on a |x − a| < 1 et |y − a| < 1.

Cela implique nécessairement a = [x] ou a = [x] + 1, et b = [y] ou b = [y] + 1.

Les solutions sont donc à chercher parmi les quatre nombres complexes :

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

Sur la figure de gauche ci-dessous, on a représenté ω = x + iy, ainsi que z1, z2, z3, z4.

On a également fait figurer les cercles de centre zk et de rayon 1.

La position du point ω est quelconque dans le carré “z1z2z4z3” (mais ω ne peut pas

appartenir aux cotés “z3z4” et “z2z4”.)

Selon la position de ω dans le carré “z1z2z4z3”, on voit que ω est toujours intérieur

a un au moins de ces cercles, mais qu’il peut être intérieur a deux, trois voire quatre

cercles (c’est le cas du complexe ω représenté ici.).

En fait ω n’est intérieur qu’a un seul cercle que si w = z1, c’est-a-dire si ω ∈ ZZi.

Ainsi, pour tout ω de lC, il y a de un à quatre éléments z de ZZi tels que |z − ω| < 1.

Sur la figure de droite ci-dessus, on a fait cette fois-ci figurer les cercles de centre zk

√

2

2 . Ces cercles passent tous par le centre du carré.

et de rayon r =

c(cid:13)EduKlub S.A.

Page 9

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

On voit que ω est à une distance ≤ r de un ou deux sommets du carré (mais les

quatre si ω est au centre, toutes les distances |zk − ω| valant alors r =

√

2

2 .)

√

Ainsi : ∀ ω = x + iy ∈ lC, ∃ z ∈ ZZi tel que |z − ω| ≤

2 donc tel que ϕ(z − ω) ≤ 1

2.

Pour tout ω = x+iy dans lC, une autre façon de justifier l’existence de z = a+ib dans

(cid:3) (les coordonnées de

ZZi tel que ϕ(z − ω) ≤ 1

z sont donc obtenues a partir de x et y par arrondi a l’entier le plus proche.) [ Q ]

2 est de poser a = (cid:2)x + 1

(cid:3) et b = (cid:2)y + 1

2

2

2

(b) Posons ω =

z0

z

. Les conditions

(cid:26) z0 = qz + r

ϕ(r) < ϕ(z)

équivalent à

(cid:26) ϕ(ω − q) < 1

r = z0 − qz

On sait qu’il y a de une à quatre solutions q dans ZZi.

Pour chacune d’elle, on obtient r = z0 − qz de façon unique.

Conclusion : il existe de un à quatre couples (q, r) de ZZ2

i tels que

(cid:26) z0 = qz + r

ϕ(r) < ϕ(z)

[ Q ]

(c) Avec les notations précédentes, on a ω =

z0

z

=

47 + 29i

25

.

ω est intérieur au carré défini par q1 = 1 + i, q2 = 2 + i, q3 = 1 + 2i, q4 = 2(1 + i).

On vérifie que ϕ(ω − q1) =

4

5

, ϕ(ω − q2) =

1

25

, ϕ(ω − q3) =

37

25

, ϕ(ω − q4) =

18

25

.

Ainsi seuls q1, q2, q4 satisfont à la condition

varphi(ω − q) < 1.

Il y a donc trois divisions possibles de z0 par z :

– z0 = (1 + i)z + 2(1 + 2i). Ici ϕ(r) = 20 (on a bien ϕ(r) < ϕ(z), car ϕ(z) = 25.)

– z0 = (2 + i)z − 1. Ici ϕ(r) = 1.

– z0 = 2(1 + i)z + 3(1 − i). Ici ϕ(r) = 18.

La “meilleure” division de z0 par z est z0 = (1 + 2i)z − 1.

[ Q ]

(d) Si z0 est dans ZZ et z dans IN∗, la division euclidienne classique de z0 par z s’écrit

z0 = qz + r, avec 0 ≤ r < z. Cette dernière condition s’écrit aussi ϕ(r) < ϕ(z)

puisque r et z sont des entiers positifs. Ainsi la division euclidienne de z0 par z dans

ZZ est aussi une division au sens de ZZi. [ Q ]

(e) Voici une solution, et un exemple d’utilisation :

> div :=proc(z1,z2) round(z1/z2) :[%,z1-%*z2] end :

> div(1+11I,3+4I) ;

[2 + I, −1]

[ Q ]

c(cid:13)EduKlub S.A.

Page 10

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

2. Algorithme d’Euclide

(a) La suite des restes successifs rk vérifie ϕ(r1) > ϕ(r2) > · · · > ϕ(rk) > · · ·

Les ϕ(rk) forment donc une suite strictement décroissante d’entiers naturels.

[ Q ]

Cette suite est nécessairement finie, et avec elle le nombre de divisions.

(b) Pour tous éléments α, β, δ de ZZi, on a Di(α) ∩ Di(β) = Di(β) ∩ Di(α − δβ).

En effet si un élément ω de ZZi divise α et β, il divise β et γ = α − δβ.

Inversement s’il divise β et γ = α − δβ, il divise β et α = γ + δβ.

Appliqué à rk−1 = qkrk + rk+1, cela donne Di(rk−1) ∩ Di(rk) = Di(rk) ∩ Di(rk+1).

Ainsi toutes les intersections Di(rk) ∩ Di(rk+1) sont égales a la premiere d’entre elles,

c’est-à-dire Di(r0) ∩ Di(r1), ou encore Di(z0) ∩ Di(z).

La dernière division est rn−1 = qnrn. Donc rn k rn−1 et Di(rn) ⊂ Di(rn−1).

Ainsi Di(z0) ∩ Di(z) = Di(rn−1) ∩ Di(rn) = Di(rn) = Di(d) (d = r+

Enfin, si δ ∈ ZZ+

n est associé à rn.)

i vérifie Di(δ) = Di(d), on a δ ∼ d puis δ = d (cf I.3.d et I.4.a) [ Q ]

(c) On prouve l’existence de (uk, vk) tel que zuk + z0vk = rk par récurrence finie sur k.

La propriété est vraie si r = 0 avec u0 = 0 et v0 = 1 (car r0 = z0).

Elle est vraie si r = 1 avec u0 = 1 et v0 = 0 (car r1 = z).

Supposons la propriété vraie aux rang k − 1 et k, avec k ∈ {1, . . . , n − 1}.

Ainsi il existe

(cid:26) (uk−1, vk−1)

(uk, vk)

D’autre part, on a rk−1 − qkrk = rk+1.

dans ZZ2

i tels que

(cid:26) zuk−1 + z0vk−1 = rk−1

zuk + z0vk = rk

(1)

(2)

(1) − qk(2) donne alors zuk+1 + z0vk+1 = rk+1 avec

(cid:26) uk+1 = uk−1 − qkuk

vk+1 = vk−1 − qkvk

uk+1 et vk+1 sont dans l’anneau ZZi, ce qui démontre la propriété au rang k + 1.

Ainsi la propriété est vraie au rang n : ∃ (un, vn) ∈ ZZ2

Or d = z ∧ z0 = r+

En posant u = ω un et v = ω vn, on obtient zu + z0v = d, avec (u, v) ∈ ZZ2

i .

[ Q ]

n : il existe donc ω dans U = {1, i, −1, −i} tel que d = ω rn.

i , zun + z0vn = rn.

(d) Les diviseurs communs de z et z0 sont les diviseurs de d = z ∧ z0.

Parmi les diviseurs de d, il y a d bien sûr et ses trois associés id, −d, −id.

Tous quatre ont même module que d. Enfin les diviseurs de d qui ne lui sont pas

associés ont un module strictement inférieur à celui de d (cf I.4.c et I.4.d).

[ Q ]

(e) Si z, z0 sont dans ZZ, l’algorithme d’Euclide “classique” dans ZZ est ainsi un algo-

rithme d’Euclide dans ZZi (cf II.1.d). Les deux algorithmes conduisent donc au même

résultat (l’un dans ZZ+

i et l’autre dans ZZ+∗) : les deux notions de pgcd co¨ıncident.

[ Q ]

c(cid:13)EduKlub S.A.

Page 11

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

3. Un peu de programmation

(a) Voici une solution, avec un exemple d’utilisation :

> 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 :

> zpos(3-2*I) ;

[ Q ]

2 + 3I

(b) Voici un calcul itératif du pgcd (on utilise les fonctions div et zpos) :

> 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 :

Voici un exemple d’utilisation. Le pgcd de 23 + 2i et de 34 + 19i est 5 + 4i :

> pgcd(23+2I,34+19I) ;

5 + 4I

[ Q ]

(c) Voici un calcul récursif du pgcd :

> rpgcd :=proc(z1,z2)

if z2=0

then zpos(z1)

else rpgcd(z2,div(z1,z2)[2]) fi

end :

On reprend le même exemple d’utilisation (le pgcd de 23 + 2i et de 34 + 19i) :

> rpgcd(23+2I,34+19I) ;

5 + 4I

[ Q ]

(d) La procédure bezout forme des couples (uk, vk) tels que zuk + z0vk = rk (avec les

notations de la question II.2.c). Pour cela, et comme il s’agit d’une récurrence de

pas 2, on maintient deux couples de variables u1, v1, u2, v2.

On reconnait l’initialisation de ces variables, correspondant aux cas r = 0 et r = 1.

Ensuite leur actualisation s’effectue parallelement a l’algorithme d’Euclide de z1, z2.

A la fin, on obtient un, vn tels que zun + z0vn = rn.

On sait qu’il existe ω inversible tel que rn = ω r+

n = ω z ∧ z0.

c(cid:13)EduKlub S.A.

Page 12

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

On termine donc en divisant les contenus de un, vn par ω.

> 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 :

Voici un exemple d’utilisation, avec z = 23 + 2I et z0 = 34 + 19i.

On trouve u = −2 + i et v = 1 − i.

> bezout(23+2I,34+19I) ;

[−2 + I, 1 − I]

On vérifie effectivement que uz + vz0 = 5 + 4i = z ∧ z0.

> (-2+I)(23+2I)+(1-I)(34+19I) ;

5 + 4I

[ Q ]

(e) On sait que si z1 = qz2 + r est la division de z1 par z2 dans ZZi, alors z1 ∧ z2 = z2 ∧ r.

Donc si z2u0 + rv0 = z2 ∧ r, alors z1 ∧ z2 = z2u0 + (z1 − qz2)v0 = z1v0 + (u0 − qv0)z2.

Ainsi un couple (u, v) vérifiant z1u+z2v = z1 ∧z2 est donné par u = v0 et v = u0 −qv0.

Cela permet de calculer récursivement un couple de coefficients de bezout.

z+

1

z1

La condition d’arrêt est z2 = 0 : dans ce cas uz1 + vz2 = z+

1 , avec u =

et v = 0.

> 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 :

On reprend le même exemple d’utilisation :

> rbezout(23+2I,34+19I) ;

[−2 + I, 1 − I]

[ Q ]

c(cid:13)EduKlub S.A.

Page 13

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

4. Entiers de Gauss premiers entre eux

(a) Si z ∧ z0 = 1, alors il existe (u, v) dans ZZ2

i tels que zu + z0u0 = 1 (cf II.2.)

Réciproquement supposons qu’il existe (u, v) dans ZZ2

i tels que zu + z0u0 = 1.

L’élément d = z ∧ z0 est un diviseur de z et de z0 donc de zu + z0u0 donc de 1.

Cela signifie que d est inversible dans ZZi.

Comme d est un élément de ZZ+

i , il vient d = 1.

[ Q ]

(b) Par hypothèse il existe q dans ZZi tel que z0z00 = qz.

D’autre part, il existe u, v dans ZZi tel que zu + z0v = 1.

On multiplie cette égalité par z00 et on trouve z00 = z00zu + (z00z0)v = z(z00u + qv).

Il en découle que z divise z00 dans ZZi, ce qu’il fallait vérifier.

(c) Par hypothèse, il existe (a, b) et (c, d) dans ZZ2

i tels que

[ Q ]

(cid:26) az + bz0 = 1

cz + dz00 = 1

On multiplie terme à terme : (adz00 + bcz0 + acz)z + (bd)z0z00 = 1.

C’est une identité de Bezout entre z et z0z00 dans ZZi.

Il en découle que z et z0z00 sont premiers entre eux dans ZZi.

On peut généraliser par une récurrence évidente :

– Si z est premier avec z0

1, z0

2, . . . , z0

n, il est premier avec leur produit.

– Si chaque zk est premier avec chaque z0

j, alors

m

Q

k=1

zk ∧

n

Q

j=1

z0

j = 1.

– Cas particulier : si z ∧ z0 = 1, alors ∀ (m, n) ∈ IN2, zm ∧ z0 n = 1.

[ Q ]

(d) Par hypothèse, il existe q et q0 dans ZZi tels que

D’autre part, il existe (u, v) dans ZZ2

Si on multiplie cette dernière égalité par z00, on trouve :

(cid:26) z00 = qz

z00 = q0z0

i tel que zu + z0u0 = 1.

z00 = z00zu + z00z0u0 = (q0z0)zu + (qz)z0u0 = (q0u + qu0)(zz0)

ce qui prouve que zz0 divise z00.

[ Q ]

Partie III. Entiers de Gauss irréductibles

1. Quelques propriétés des éléments de Pi

(a) C’est évident car z et z+ sont associés, et parce que Di(z) = Di(z+).

(b) On se donne p dans Pi, z dans ZZi, et on suppose que p ne divise pas z.

[ Q ]

Soit d ∈ ZZi un diviseur de p et z.

Puisque d k p et p ∈ Pi, on a d ∈ U ou d ∈ ep.

c(cid:13)EduKlub S.A.

Page 14

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Problèmes de Mathématiques

Entiers de Gauss

Corrigé

Il est impossible que d soit associé à p, car p ne divise pas z.

Donc d ∈ U, ce qui implique p ∧ z = 1 : p et z sont premiers entre eux.

Soient p et q dans P +

égal à q car tous deux sont dans P +

i . Si p k q alors p (qui n’est pas inversible) est associé à q (donc

i , cf I.3.d.)

Autrement dit, si p 6= q alors p ne divise pas q donc p ∧ q = 1.

[ Q ]

(c) Soient p, z, z0 dans ZZi. On suppose que p est dans Pi et que p k (zz0).

Si p divise z, c’est terminé. Sinon la question précédente donne p ∧ z = 1.

Ainsi p k (zz0) et p ∧ z = 1 : le théorème de Gauss donne p k z0.

Une récurrence évidente montre que si p k

n

Q

k=1

zk, alors ∃ k ∈ {1, . . . , n}, p k zk. [ Q ]

(d) On suppose que ϕ(z) est un...