142 – PGCD et PPCM, algorithmes de calcul. Applications.

Références : Rombaldi, Gourdon Algèbre, Perrin, Mathématiques L1 : Cours complet Définition 11. Soit P ∈ A[X] (A factoriel), on définit le contenu de P comme étant
avec 1000 tests et exercices corrigés Marco. le PGCD de ses coefficients. On le note c(P).
Cadre : (A, +, ×) un anneau intègre. L’objectif est de généraliser les notions de
PGCD et PPCM connus sur N sur des anneaux. Lemme 12. Lemme de Gauss pour les polynômes. c(P Q) = c(P )c(Q)

Théorème 13 (Critère d’irreductibilité d’Eisenstein). Soit P =

Xn

1 Définition du PGCD et PPCM sur un ak X k ∈ A[X] et p un nombre premier. On suppose que p|ai ∀i ∈ {0, ..., n−
k=0
anneau factoriel 1}, p ne divise pas an et p2 ne divise pas a0 . Alors P est un polynôme irre-
ductible de FracA[X]
Définition 1. Soit (a, b) ∈ A. On dit que a divise b si il existe c ∈ A tel que b = ac.
/ A× et a = bc =⇒ b ∈ A× ouc ∈ A× .
On dit que a est irreductible si a ∈
On dit que a est premier si a ∈/ A et a|bc =⇒ a|b ou a|c.
Définition 2. Un anneau A est dit factoriel si pour tout a ∈ A non-inversible, il 2 Anneaux principeaux et relation de
existe des éléments irreductibles (p1 , ..., pr ) de A et un élément inversible u tel que
a = u × p1 × ... × pr . Cette décomposition est unique à l’ordre des facteurs près. Bézout
Proposition 3. Dans un anneau factoriel, p est premiers ⇐⇒ p est irreductible. Définition 14. Un anneau A est dit principal si tout les idéaux I de A peuvent
Exemple 4. Z, K[X] avec K un corps sont des anneaux factoriels. s’écrire I=(a) avec a un élément de A
Définition 5. Soit a,b dans A, avec les décompositions a = uΠri=1 pni i et b = Proposition 15. Si a|b, on à (b) ⊂ (a).
vΠri=1 pm
i i avec ni , mi des entiers éventuellement nul.
On définit le PGCD de deux élément par a ∧ b = Πri=1 pi
min(ni ,mi )
et le PPCM par Proposition 16. Un anneau principal est factoriel
r max(n i ,m i )
a ∨ b = Πi=1 pi Remarque 17. Il est possible de définir autrement le PGCD et le PPCM sur
Remarque 6. Il n’y a pas unicité du PGCD et du PPCD puisqu’ils sont définies à un anneau principal. Cette nouvelle définition est équivalente à celle donnée
un inversible près. précédemment.
On définit par reccurence le PGCD et PPCM de n éléments. Définition 18. Soit A principal. On appelle PGCD de (a1 , ...an ) l’élément qui en-
Deux éléments sont dits premiers entre eux si a ∧ b ∈ A× . gendre l’idéal (a1 ) + ... + (an ). On appelle PPCM l’élément qui engendre l’idéal
Proposition 7. — Si c divise a et b, alors c divise a ∧ b (a1 ) ∩ ... ∩ (an )
— si a et b divise c, alors a ∨ b divise c. Théorème 19 (Relation de Bézout). d = a1 ∧ ... ∧ an ⇐⇒ il existe des éléments
(u1 , ..., un ) dans A tel que d = a1 u1 + ... + an un .
Exemple 8. 6 ∧ 21 = 3 dans Z.
X 2 − 1 ∧ X − 1 = X − 1 dans R[X] Application 20 (Lemme des noyaux). Soit E un K-espace vectoriel de dimension
X 2 − 9 ∨ X 2 + 5X + 6 = (X 2 − 9)(X + 2) dans R[X]. n et f ∈ L(E). Soit P = P1 ...Pr avec Pi ∈ K[X] des polynômes premiers entre eux
r
Proposition 9. Soit (λ, a1 , ..., an ) ∈ A∗ . Alors λa1 ∧ ... ∧ λan = λa1 ∧ ... ∧ an . (De
M
deux à deux. Alors Ker(P (f )) = Ker(Pi (f )).
même pour le PPCM). i=1

Proposition 10. Pour tout a, b ∈ A, a ∧ b × a ∨ b = a × b à un inversible près. Donc Corollaire 21 (Lemme de Gauss). Si a|bc et a et b sont premiers entre eux, alors
si a et b sont premiers entre eux, on à a ∨ b = ab à un inversible près. a|c.
Théorème 22 (Des restes chinois). Soient (n1 , ..., nr ) des éléments de A prin- Lemme28 (d’Euclide). On reprend les notations de la définition précédente.
cipal premiers deux à deux entre eux. On pose n = n1 × ... × nr . Alors on à b si r = 0
A A a∧b=
A
' × ... × à l’aide de l’application : b ∧ r sinon.
(n) ϕ (n1 ) (nr )
Méthode 29 (D’euclide). On donne l’algorithme d’Euclide qui permet de calculer
A A A le PGCD de deux éléments. (voir Rombaldi)
ϕ: → × ... × (1)
(n) (n1 ) (nr ) Application 30. 157 ∧ 24 = 1
πn (a) 7→ (πn1 (a), ..., πnr (a)) 424 ∧ 68 = 4
5n+1 − 1 ∧ 5n − 1 = 4
X5 − X4 + X3 − X2 + X − 1 ∧ X2 − 1 = X − 1
L’application réciproque est X3 + X2 + X + 1 ∧ X + 1 = X + 1

A A A
ϕ−1 : × ... × → (2) 3.2 Algorithme d’Euclide étendu
(n1 ) (nr ) (n)
r
X n
(πn1 (a1 ), ..., πar (k)) 7→ πn ( ai ui ) Méthode 31. En remontant l’algorihme d’Euclide, on est capable de déterminer
ni
i=1 une relation de Bézout.
r Exemple 32. 1 = 72 × 24 − 11 × 157
X n X +2 X −1
où les (ui ) ∈ Ar vérifient : ui =1 Pour X − 1 et X + 2 on à : − =1
i=1
ni 3 3
Remarque 23. Ce théorème permet de résoudre des systèmes de congruence dans X 2 − 2X + 1 X − 3
Z où K[X]. Mais pour cela, on à besoin d’être capable de calculer des relations de Pour X + 1 et X 2 − 2X + 1 on à : − (X + 1) = 1
4 4
Bézouts ! C’est le but de la prochaine partie. Théorème 33 (De Bézout). d = a1 ∧ ... ∧ an ⇐⇒ Il existe des entiers relatifs
(u1 , ..., un ) tel que d = a1 u1 + ... + an un .
Théorème 24 (de l’élément primitif ). Soit K un corps commutatif de Méthode 34 (Algorithme d’Euclide). On est concrètement capable de construire
caractéristique nulle et L un surcorps de K. Si L est un K-e.v de dimension les entiers (u1 , ..., un ) précédents grâce à l’algorithme d’Euclide.
finie, alors il existe x ∈ L telle que L = K[x]
Exemple 35. 157 ∧ 24 = 1 puis 1 = 72 × 24 − 11 × 157

3.3 Application à la résolution d’équation diophantienne

3 Anneaux euclidiens et algorithmes de
Théorème 36 (Equation diophantienne de degré 2). On considère l’équation
calculs ax + by = c, avec a,b et c trois entiers relatifs.
Cette équation admet des solutions ⇐⇒ a ∧ b divise c.
k
3.1 Algorithme d’Euclide, calcul de PGCD Dans ce cas, l’ensemble des solutions est les couples (x, y) = (x0 , y0 ) + (b, −a
a∧b
avec k ∈ Z, avec (x0 , y0 ) une solution particulière de l’équation (donnée par l’algo-
Définition 25. Un anneau A est dit euclidien si il existe un stahtme ϕ, une appli- rithme d’Euclide étendue).
cation de A 7→ N tel que ∀(a, b) ∈ A, avec b 6= 0, il existe un couple (q, r) ∈ A2 tel Exemple 37. — Pour l’équation 3x + 2y = 5, l’ensemble des solutions est
que a = bq + r avec r = 0 où ϕ(r) < ϕ(b). (5, −5) + k × (2, −3), pour k ∈ Z.
Exemple 26. Z est un anneau euclidien avec le stathme valeur absolue. — L’équation 12x + 8y = 5 n’admet pas de solutions.
K[X] est un anneau euclidien avec le degré pour stathme
Théorème 38. On s’intéresse à l’équation de congruence ax ≡ b (mod n), avec
Théorème 27. Un anneau euclidien est principal. n > 1, a un entier naturel et b un entier relatif.
 Z
— Si b=1, cette équation à des solutions ⇐⇒ a est inversible dans ⇐⇒ a
nZ
est premier avec n.
Dans ce cas, l’ensemble des solutions est x0 + kn, où x0 est une solution par-
ticulière de ax ≡ 1 (mod n)
— Si b est qcq et a ∧ n = 1. Alors u0 = bx0 est une solution particulière avec x0
solution de ax ≡ 1 (mod n). L’ensemble des solutions de ax ≡ b (mod n) est
alors {u0 + kn|k ∈ Z}.
— Le cas général : l’équation ax ≡ b (mod n) admet des solutions ⇐⇒
δ = a ∧ n|b.
b n
Dans ce cas, les solutions sont les entiers de la forme : x00 + k avec k ∈ Z
δ δ
0 a b n
et x0 une solution particulière de l’équation x ≡ (mod )
δ δ δ
Exemple 39. Grâce au théorème chinois, on peut résoudre certains systèmes de
congruence :
Le système :

 k≡2 (mod 4)
k≡3 (mod 5)
k≡1 (mod 9)


admet pour solution les entiers de la forme 838 + 180k pour k ∈ Z.