Probl`emes de Math´ematiques
Entiers de Gauss
´Enonc´e
Entiers de Gauss
– On note ZZi = {a + ib, a ∈ ZZ, b ∈ ZZ}. Les ´el´ements de ZZi sont appel´es entiers de Gauss.
Dans suite, quand on dira soit z = a + ib dans ZZi, il sera sous-entendu que a, b sont dans ZZ.
– Pour tout ´el´ement z = a + ib de ZZi, on note ϕ(z) = zz = |z|2 = a2 + b2.
Bien sˆur ϕ(z) est dans IN et pour tous z, z0 de ZZi on a ϕ(zz0) = ϕ(z)ϕ(z0).
– On note ZZ+
i
l’ensemble des z = a + ib de ZZi tels que a ≥ 1 et b ≥ 0.
Partie I. Divisibilit´e dans l’anneau ZZi.
1. Montrer que (ZZi, +, ×) est anneau. Que dire de ZZ relativement `a ZZi ? [ S ]
2. Montrer que les seuls ´el´ements inversibles de l’anneau ZZi sont 1, i, −1, −i.
Dans toute la suite, on notera U = {1, i, −1, −i}. [ S ]
3. On dit que z divise z0 dans ZZi s’il existe q dans ZZi tel que z0 = qz.
On note alors z k z0 (on d´efinit ainsi une relation r´eflexive et transitive sur ZZi.)
Remarque : on note toujours m | n la relation divisibilit´e dans ZZ.
(a) Soient z, z0 deux ´el´ements de ZZ, donc de ZZi. Montrer que z | z0 ⇔ z k z0.
Autrement dit la relation de divisibilit´e dans ZZi “prolonge” celle de ZZ. [ S ]
(b) Soient z et z0 dans ZZi. Montrer que (z k z0 et z0 k z) ⇔ ∃ u ∈ U, z0 = uz.
On exprimera cette situation en disant que z et z0 sont associ´es dans ZZi.
Dans toute la suite on notera z ∼ z0 pour exprimer que z et z0 sont associ´es. [ S ]
(c) Montrer que la relation ∼ est une relation d’´equivalence sur ZZi.
On notera ez la classe d’´equivalence d’un ´el´ement z de ZZi.
Quel est le cardinal de ez ? Que repr´esente g´eom´etriquement ez ? [ S ]
(d) Soit z 6= 0 dans ZZi. Montrer que ZZ+
i contient un unique ´el´ement de ez.
Dans la suite du probl`eme, cet ´el´ement sera not´e z+. [ S ]
4. Dans cette question, z et z0 sont deux ´el´ements quelconques de ZZi.
On note Di(z) = {ω ∈ ZZi, ω k z} l’ensemble des diviseurs de z dans ZZi.
On note zZZi = {zω, ω ∈ ZZi} l’ensemble des multiples de z dans ZZi.
(a) Montrer que zZZi ⊂ z0ZZi ⇔ z0 k z ⇔ Di(z0) ⊂ Di(z).
En d´eduire zZZi = z0ZZi ⇔ z0 ∼ z ⇔ Di(z) = Di(z0).
[ S ]
(b) Montrer que z divise ϕ(z) dans ZZi.
(cid:26) z0 k z ⇒ ϕ(z0) | ϕ(z)
[ S ]
(c) Montrer que
z0 ∼ z ⇒ ϕ(z0) = ϕ(z)
et que les r´eciproques sont fausses.
[ S ]
(d) Montrer que si z0 k z et ϕ(z) = ϕ(z0), alors z0 ∼ z.
(e) D´eterminer Di(4 + 7i) ∩ ZZ+
i , puis Di(4 + 7i).
[ S ]
[ S ]
c(cid:13)EduKlub S.A.
Page 1
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
´Enonc´e
Partie II. Division et pgcd dans ZZi.
1. Division euclidienne
(a) Soit ω un ´el´ement de lC.
Montrer qu’il existe de un `a quatre ´el´ements z de ZZi tel que |z − ω| < 1.
Montrer qu’il existe au moins un ´el´ement z de ZZi tel que |z − ω| ≤ 1
2 .
[ S ]
(b) Soient z, z0 deux ´el´ements de ZZi, z ´etant non nul.
Montrer qu’il existe de un `a quatre couples (q, r) de ZZ2
Cette ´ecriture est appel´ee une division de z0 par z dans ZZi.
Dans une telle division, q est appel´e le quotient et r est appel´e le reste.
i tels que
[ S ]
(cid:26) z0 = qz + r
ϕ(r) < ϕ(z)
(c) Ecrire toutes les divisions possibles dans ZZi de z0 = 1 + 11i par z = 3 + 4i.
Quelle est la meilleure division (celle donnant le reste de module minimum) ? [ S ]
(d) Soient z0 dans ZZ et z dans IN∗. V´erifier que la division euclidienne de z0 par z dans
ZZ (donc au sens habituel) est aussi une division de z0 par z dans ZZi.
[ S ]
(e) Ecrire une proc´edure Maple, sur le mod`ele div :=proc(z1,z2)...end, prenant en
argument deux nombres complexes z1 et z2 (´ecrits sous la forme x + iy) et renvoyant
la liste [q, r] repr´esentant une division de z1 par z2 dans ZZi.
Pour choisir q, on utilisera la fonction round qui accepte un complexe x + iy et
renvoie le complexe obtenu par arrondi de x, y aux entiers les plus proches. [ S ]
2. Algorithme d’Euclide
Dans cette question, on va prouver la proposition suivante :
Proposition
Soient z et z0 deux ´el´ements de ZZi, non tous les deux nuls.
Il existe un unique ´el´ement d de ZZ+
Autrement dit, pour tout ω de ZZi, on a (ω k z et ω k z0) ⇔ ω k d.
On dit que d est le pgcd de z et z0 dans ZZi. On note d = pgcd (z, z0) ou d = z ∧ z0.
Il existe un couple u, v d’´el´ements de ZZi tels que zu + z0v = d.
On dit que (u, v) est un couple de coefficients de Bezout du couple (z, z0).
i tel que Di(z) ∩ Di(z0) = Di(d).
On compl`ete cette d´efinition en posant 0 ∧ 0 = 0.
Pour d´emontrer cette proposition, on va mettre en œuvre un algorithme d’Euclide.
Les ´el´ements z et z0 jouant un rˆole sym´etrique, on peut supposer z 6= 0.
– On pose r0 = z0 et r1 = z. On note r0 = q1r1 + r2 une division de r0 par r1 dans ZZi.
– Si r2 6= 0, on note r1 = q2r2 + r3 une division de r1 par r2 dans ZZi.
– Soit n un entier de IN∗. On suppose qu’on a form´e rk et que rk est non nul.
On note alors rk−1 = qkrk + rk+1 une division de rk−1 par rk dans ZZi.
– Si rk+1 6= 0, on poursuit l’algorithme, sinon on arrˆete, et rk est le dernier reste non nul
obtenu par cette m´ethode.
c(cid:13)EduKlub S.A.
Page 2
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
´Enonc´e
(a) Montrer que l’algorithme se termine au bout d’un nombre fini de divisions. [ S ]
(b) Il existe donc un entier n tel que rn 6= 0 et rn+1 = 0. On pose d = r+
n .
Prouver ∀ k ≤ n, Di(z) ∩ Di(z0) = Di(rk) ∩ Di(rk+1), puis Di(z) ∩ Di(z0) = Di(d).
Montrer que d est le seul ´el´ement de ZZ+
(c) Montrer que : ∀ k ∈ {0, . . . , n}, ∃ (uk, vk) ∈ ZZ2
i `a v´erifier cette propri´et´e.
i , zuk + z0vk = rk.
[ S ]
En d´eduire qu’il existe (u, v) dans ZZ2
Ceci ach`eve la d´emonstration de la proposition.
i tels que zu + z0v = d.
[ S ]
(d) Montrer que parmi les diviseurs communs de z et z0, l’´el´ement z ∧ z0 et ses trois
associ´es sont ceux qui ont le plus grand module.
[ S ]
(e) Montrer que si z, z0 ∈ ZZ, leur pgcd (au sens habituel) est z ∧ z0 au sens de ZZi.
[ S ]
3. Un peu de programmation
Les proc´edures Maple demand´ees ici prennent en argument un ou deux ´el´ements de ZZi,
qui sont suppos´es ´ecrits sous la forme z = x+iy, avec x, y entiers relatifs. On ne proc´edera
donc `a aucune v´erification de la validit´e des arguments.
On rappelle d’autre part que Maple ´evalue automatiquement les expressions arithm´etiques
(sommes, produits, quotients, puissances, ...) form´ees `a partir de nombres complexes
donn´es explicitement sous la forme z = x + iy.
(a) Ecrire une proc´edure Maple, sur le mod`ele zpos :=proc(z)...end, prenant en ar-
gument un ´el´ement z de ZZi, et renvoyant z+.
[ S ]
(b) Ecrire une proc´edure Maple, sur le mod`ele pgcd :=proc(z1,z2)...end, calculant
le pgcd de deux entiers de Gauss z1 et z2, de mani`ere it´erative.
[ S ]
(c) Ecrire une proc´edure Maple, sur le mod`ele rpgcd :=proc(z1,z2)...end, calculant
le pgcd de deux entiers de Gauss z1 et z2, de mani`ere r´ecursive.
[ S ]
(d) Ecrire une proc´edure Maple, sur le mod`ele bezout :=proc(z1,z2)...end, calculant
un couple de coefficients de Bezout de z1, z2. Le r´esultat sera une liste [u, v] telle que
zu + z0v = z ∧ z0. La proc´edure bezout calculera u, v de mani`ere it´erative.
[ S ]
(e) Ecrire une proc´edure Maple, sur le mod`ele rbezout :=proc(z1,z2)...end, et qui
effecte le mˆeme calcul que bezout mais de mani`ere r´ecursive. [ S ]
4. Entiers de Gauss premiers entre eux
On dit que deux ´el´ements z, z0 de ZZi sont premiers entre eux dans ZZi si z ∧ z0 = 1.
Remarque : il d´ecoule de II.2.e que si z et z0 sont dans ZZ, alors ils sont premiers entre
eux en tant qu’´el´ements de ZZ si et seulement si ils le sont en tant qu’´el´ements de ZZi.
Dans les questions suivantes z, z0 et z00 sont des ´el´ements de ZZi.
(a) Montrer que z ∧ z0 = 1 ⇔ ∃ (u, v) ∈ ZZ2
i , zu + z0v = 1 (Bezout.) [ S ]
(b) Montrer que si z k (z0z00) dans ZZi, et si z ∧ z0 = 1, alors z k z00 (Gauss.) [ S ]
(c) Montrer que si z ∧ z0 = 1 et z ∧ z00 = 1 alors z ∧ (z0z00) = 1. G´en´eraliser.
[ S ]
(d) Montrer que si z k z00 et z0 k z00, et si z ∧ z0 = 1, alors (zz0) k z00.
[ S ]
Publicité
c(cid:13)EduKlub S.A.
Page 3
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
´Enonc´e
Partie III. Entiers de Gauss irr´eductibles
D´efinition
On dit que z est irr´eductible dans ZZi si z est non nul, non inversible, et si ses seuls diviseurs
sont les ´el´ements de U = {1, i, −1, −i} et les associ´es de z c’est-`a-dire z, iz, −z, −iz.
On note Pi l’ensemble des ´el´ements irr´eductibles de ZZi.
On note comme d’habitude P l’ensemble des entiers naturels premiers.
1. Quelques propri´et´es des ´el´ements de Pi
(a) Montrer z ∈ Pi ⇔ z+ ∈ Pi. On pose P +
i = Pi ∩ ZZ+
i seront appel´es facteurs irr´eductibles normalis´es. [ S ]
i = {a + ib ∈ Pi, a ≥ 1, b ≥ 0}
Les ´el´ements de P +
(b) Soient p dans Pi et z dans ZZi. Montrer que si p ne divise pas z, alors p ∧ z = 1.
En d´eduire que si p et q sont distincts dans P +
i , alors p ∧ q = 1.
[ S ]
(c) Soit p un ´el´ement de Pi. Montrer que si p k (zz0), alors p k z ou p k z0.
Plus g´en´eralement, montrer que si p k
n
Q
k=1
zk, alors ∃ k ∈ {1, . . . , n}, p k zk. [ S ]
(d) Montrer que si ϕ(z) est dans P, alors z est dans Pi. [ S ]
2. Factorisation en produit de facteurs irr´eductibles normalis´es
Soit z un ´el´ement de ZZi, non nul et non inversible (donc tel que ϕ(z) > 1.)
(a) Montrer que z est divisible par au moins un ´el´ement p de P +
i .
[ S ]
(b) Montrer que z peut s’´ecrire sous la forme z = u
m
Q
k=1
pnk
k , o`u :
– u est un ´el´ement de U = {1, i, −1, −i}. ; m est un ´el´ement de IN∗
– pour tout k de {1, . . . , m}, pk est dans ZZ+
[ S ]
i et nk dans IN∗.
(c) Montrer que l’´ecriture pr´ec´edente de z est unique a l’ordre pres des facteurs.
[ S ]
3. Irr´eductibilit´e des ´el´ements de IN∗.
Il est clair que si n ≥ 2 est un entier non premier, il n’est pas irr´eductible dans ZZi (ses
diviseurs dans IN ´etant aussi des diviseurs dans ZZi). Il reste donc `a comprendre quand un
entier premier p est irr´eductible dans ZZi. Pour cela on va d´emontrer le r´esultat suivant :
Proposition
Soit p un nombre premier. Les conditions suivantes sont ´equivalentes :
– p n’est pas irr´eductible dans ZZi.
– Il existe a et b dans IN∗ tels que p = a2 + b2.
– p = 2, ou p est congru `a 1 modulo 4.
(a) Montrer que si p n’est pas irr´eductible, alors ∃ (a, b) ∈ (IN∗)2, p = a2 + b2 (utiliser
un diviseur de p dans ZZi, non inversible et non associ´e `a p.) [ S ]
c(cid:13)EduKlub S.A.
Page 4
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
´Enonc´e
(b) Inversement, si p = a2 + b2 (avec a, b dans IN∗) montrer que p n’est pas irr´eductible
et ´ecrire la factorisation de p en produit de facteurs irr´eductibles normalis´es.
En d´eduire 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´eductible dans ZZi. [ S ]
(d) On rappelle le th´eor`eme 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´eductible.
Montrer que p divise m + i ou m − i et aboutir `a une contradiction.
Donc si p est premier et congru `a 1 modulo 4, il n’est pas irr´eductible. [ S ]
(e) Montrer que si p ≡ 3 (4), alors p est irr´eductible (raisonner par l’absurde.)
Autrement si, si p n’est pas irr´eductible, il est ´egal a 2, ou congru a 1 modulo 4.
Ceci termine la d´emonstration de la proposition.
Le r´esultat de cette question peut ˆetre r´esum´e ainsi : Un entier n ≥ 1 est irr´eductible
dans ZZi si et seulement si
(cid:26) n est premier
n ≡ 3 (4)
[ S ]
4. El´ements irr´eductibles normalis´es de ZZi.
La question pr´ec´edente indique quels ´el´ements de IN∗ sont irr´eductibles.
Pour ce qui est des ´el´ements de ZZ+
i , il reste `a ´etablir le r´esultat suivant :
Proposition
Soit z = a + ib, avec a ∈ IN∗ et b ∈ IN∗.
z est irr´eductible si et seulement si ϕ(z) = a2 + b2 est un entier premier.
De plus cet entier premier est ´egal a 2, ou est congru a 1 modulo 4.
On sait d´eja que si ϕ(z) est un entier premier, alors z est irr´eductible (cf III.1.d.)
La question III.3.e) a ´egalement montr´e qu’un entier premier congru `a 3 modulo 4 (donc
qui n’est ni ´egal a 2 ni congru a 1 modulo 4) n’est jamais la somme de deux carr´es.
Il reste donc a supposer que z = a + ib (a, b ≥ 1) est dans Pi et a montrer que ϕ(z) ∈ P.
(a) En consid´erant la d´ecomposition 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´ec´edentes, montrer que ϕ(z) = p.
[ S ]
On a ainsi obtenu la caract´erisation des ´el´ements irr´eductibles normalis´es de ZZi :
Proposition
Un ´el´ement de z = a + ib de ZZ+
– Ou bien : b = 0 et a est un nombre premier congru `a 3 modulo 4.
– Ou bien : b ≥ 1 et a2 + b2 est un nombre premier non congru `a 3 modulo 4.
i (a ≥ 1, b ≥ 0) est irr´eductible si et seulement si :
c(cid:13)EduKlub S.A.
Page 5
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
Corrig´e du probl`eme
Partie I. Divisibilit´e dans l’anneau ZZi.
1. Il suffit de v´erifier 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ˆeme 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ˆur un sous-anneau de ZZi.
car ac − bd et ad + bc sont ´el´ements de ZZ.
car a − c et b − d sont ´el´ements 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’´egalit´e 1 = ϕ(1) = ϕ(zz0) = ϕ(z)ϕ(z0).
ϕ(z) et ϕ(z0) ´etant des entiers naturels, cela implique ϕ(z) = 1.
R´eciproquement, si ϕ(z) = a2 + b2 = 1, alors z = a − ib ∈ ZZi et zz = 1.
Conclusion : un ´el´ement z = a + ib de ZZi est inversible⇔ ϕ(z) = a2 + b2 = 1.
Il y a quatre solutions, qui sont les points a coordonn´ees entieres du cercle unit´e.
Les seuls ´el´ements inversibles de ZZi sont donc 1, i, −1, −i.
(a) Soient z et z0 deux ´el´ements de ZZ, donc deux ´el´ements de ZZi.
[ Q ]
3.
– Supposons que z divise z0 dans ZZ, c’est-`a-dire qu’il existe q dans ZZ tel que z0 = qz.
Alors z divise z0 dans ZZi car q est aussi un ´el´ement de ZZi.
– R´eciproquement, supposons que z0 divise z dans ZZi.
Il existe donc un ´el´ement 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´e dans ZZi prolonge celle de ZZ.
[ Q ]
(b) Soient z et z0 deux ´el´ements 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´eciproquement, supposons z k z0 et z0 k z.
Il existe donc deux ´el´ements q, q0 de ZZi tels que z0 = qz et z = q0z0.
On en d´eduit z(qq0 − 1) = 0 donc z = 0 ou qq0 = 1.
Si z = 0, alors z0 = 0 et on peut bien ´ecrire z0 = uz pour tout u de U.
Sinon qq0 = 1 montre que q et q0 sont deux ´el´ements 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 ]
Publicité
c(cid:13)EduKlub S.A.
Page 6
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
(c) – Pour tout z de ZZi, on a z = uz avec u = 1. La relation ∼ est donc r´eflexive.
– Si z0 = uz, avec u ∈ U, alors z = vz0, avec v = u ∈ U : ∼ est sym´etrique.
– Si
n z0 = uz
z00 = vz0 avec (u, v) ∈ U, alors z00 = wz, avec w = vu ∈ U : ∼ est transitive.
– Conclusion : la relation ∼ est d’´equivalence sur ZZi.
Pour tout z de ZZi, ez = {z, iz, −z, −iz}. Si z = 0 alors ez = {0}, sinon Card ez = 4.
Interpr´etation g´eom´etrique : pour tout z de ZZi, les points-images des ´el´ements de ez
sont les sommets du carr´e de centre 0 donc un sommet est m(z).
Remarque : les ´el´ements de ez sont les solutions ω de ω4 = z4. La relation d’association
aurait d’ailleurs pu ˆetre d´efinie par z ∼ z0 ⇔ z4 = z04, ce qui fait imm´ediatement
apparaˆıtre qu’il s’agit d’une relation d’´equivalence.
[ Q ]
(d) Soit ϕ l’application de lC dans lC d´efini 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 ´el´ement 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´ema ci-dessous, on a fait figurer z = −4+3i et ses trois associ´es 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
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´eduit : zZZi ⊂ z0ZZi ⇔ z0 k z ⇔ Di(z0) ⊂ Di(z).
Il en d´ecoule : 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 ´el´ement de ZZi. Donc z k ϕ(z).
[ Q ]
(c) Supposons z0 k z : il existe q dans ZZi tel que z = qz0.
On en d´eduit ϕ(z) = ϕ(q)ϕ(z0), avec ϕ(q) ∈ IN. Donc ϕ(z0) divise ϕ(z) dans ZZ.
La r´eciproque 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ˆeme 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´es.
Sinon ∃ q ∈ ZZi, q 6= 0, z = qz0. Alors ϕ(z) = ϕ(q)ϕ(z0) = ϕ(q)ϕ(z) ⇒ ϕ(q) = 1.
Cela prouve que q est ´el´ement de u, donc que z et z0 sont associ´es.
[ Q ]
(e) Posons z = 4 + 7i. On cherche un diviseur ω = x + iy dans ZZ+
i (x ∈ IN∗ et y ∈ IN.)
N´ecessairement ϕ(ω) 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
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´es de ceux qui appartiennent `a 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´ecessairement a = [x] ou a = [x] + 1, et b = [y] ou b = [y] + 1.
Les solutions sont donc `a 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´esent´e ω = x + iy, ainsi que z1, z2, z3, z4.
On a ´egalement fait figurer les cercles de centre zk et de rayon 1.
La position du point ω est quelconque dans le carr´e “z1z2z4z3” (mais ω ne peut pas
appartenir aux cot´es “z3z4” et “z2z4”.)
Selon la position de ω dans le carr´e “z1z2z4z3”, on voit que ω est toujours int´erieur
a un au moins de ces cercles, mais qu’il peut ˆetre int´erieur a deux, trois voire quatre
cercles (c’est le cas du complexe ω repr´esent´e ici.).
En fait ω n’est int´erieur 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 `a quatre ´el´ements 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´e.
et de rayon r =
c(cid:13)EduKlub S.A.
Page 9
Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
Publicité
On voit que ω est `a une distance ≤ r de un ou deux sommets du carr´e (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¸con de justifier l’existence de z = a+ib dans
(cid:3) (les coordonn´ees 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)
´equivalent `a
(cid:26) ϕ(ω − q) < 1
r = z0 − qz
On sait qu’il y a de une `a quatre solutions q dans ZZi.
Pour chacune d’elle, on obtient r = z0 − qz de fa¸con unique.
Conclusion : il existe de un `a quatre couples (q, r) de ZZ2
i tels que
(cid:26) z0 = qz + r
ϕ(r) < ϕ(z)
[ Q ]
(c) Avec les notations pr´ec´edentes, on a ω =
z0
z
=
47 + 29i
25
.
ω est int´erieur au carr´e d´efini par q1 = 1 + i, q2 = 2 + i, q3 = 1 + 2i, q4 = 2(1 + i).
On v´erifie que ϕ(ω − q1) =
4
5
, ϕ(ω − q2) =
1
25
, ϕ(ω − q3) =
37
25
, ϕ(ω − q4) =
18
25
.
Ainsi seuls q1, q2, q4 satisfont `a 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’´ecrit
z0 = qz + r, avec 0 ≤ r < z. Cette derni`ere condition s’´ecrit 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
2. Algorithme d’Euclide
(a) La suite des restes successifs rk v´erifie ϕ(r1) > ϕ(r2) > · · · > ϕ(rk) > · · ·
Les ϕ(rk) forment donc une suite strictement d´ecroissante d’entiers naturels.
[ Q ]
Cette suite est n´ecessairement finie, et avec elle le nombre de divisions.
(b) Pour tous ´el´ements α, β, δ de ZZi, on a Di(α) ∩ Di(β) = Di(β) ∩ Di(α − δβ).
En effet si un ´el´ement ω de ZZi divise α et β, il divise β et γ = α − δβ.
Inversement s’il divise β et γ = α − δβ, il divise β et α = γ + δβ.
Appliqu´e `a 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 ´egales a la premiere d’entre elles,
c’est-`a-dire Di(r0) ∩ Di(r1), ou encore Di(z0) ∩ Di(z).
La derni`ere 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´e `a rn.)
i v´erifie 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´ecurrence finie sur k.
La propri´et´e 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´et´e 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´emontre la propri´et´e au rang k + 1.
Ainsi la propri´et´e 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ˆur et ses trois associ´es id, −d, −id.
Tous quatre ont mˆeme module que d. Enfin les diviseurs de d qui ne lui sont pas
associ´es ont un module strictement inf´erieur `a 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ˆeme
r´esultat (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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
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´eratif 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
Publicité
[ Q ]
(c) Voici un calcul r´ecursif 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ˆeme exemple d’utilisation (le pgcd de 23 + 2i et de 34 + 19i) :
> rpgcd(23+2I,34+19I) ;
5 + 4I
[ Q ]
(d) La proc´edure 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´ecurrence 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
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´erifie 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´erifiant z1u+z2v = z1 ∧z2 est donn´e par u = v0 et v = u0 −qv0.
Cela permet de calculer r´ecursivement un couple de coefficients de bezout.
z+
1
z1
La condition d’arrˆet 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ˆeme 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
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´eciproquement supposons qu’il existe (u, v) dans ZZ2
i tels que zu + z0u0 = 1.
L’´el´ement 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 ´el´ement de ZZ+
i , il vient d = 1.
[ Q ]
(b) Par hypoth`ese 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 ´egalit´e par z00 et on trouve z00 = z00zu + (z00z0)v = z(z00u + qv).
Il en d´ecoule que z divise z00 dans ZZi, ce qu’il fallait v´erifier.
(c) Par hypoth`ese, il existe (a, b) et (c, d) dans ZZ2
i tels que
[ Q ]
(cid:26) az + bz0 = 1
cz + dz00 = 1
On multiplie terme `a terme : (adz00 + bcz0 + acz)z + (bd)z0z00 = 1.
C’est une identit´e de Bezout entre z et z0z00 dans ZZi.
Il en d´ecoule que z et z0z00 sont premiers entre eux dans ZZi.
On peut g´en´eraliser par une r´ecurrence ´evidente :
– 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`ese, il existe q et q0 dans ZZi tels que
D’autre part, il existe (u, v) dans ZZ2
Si on multiplie cette derni`ere ´egalit´e 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´eductibles
1. Quelques propri´et´es des ´el´ements de Pi
(a) C’est ´evident car z et z+ sont associ´es, 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Probl`emes de Math´ematiques
Entiers de Gauss
Corrig´e
Il est impossible que d soit associ´e `a 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 +
´egal `a q car tous deux sont dans P +
i . Si p k q alors p (qui n’est pas inversible) est associ´e `a 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´e. Sinon la question pr´ec´edente donne p ∧ z = 1.
Ainsi p k (zz0) et p ∧ z = 1 : le th´eor`eme de Gauss donne p k z0.
Une r´ecurrence ´evidente 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...