142 PGCD et PPCM, algorithmes de calcul. Applications.

PGCD et PPCM, algorithmes de calcul. Applications.

algebra

Notion de PGCM/PPCM dans un anneau

Soit $A$ un anneau commutatif unitaire.

[ULM18]
p. 39

Définition 1. Soient $a, b \in A$ .

On dit que $a$ divise $b$ (ou que $b$ est un multiple de $a$ ), noté $a ∣ b$ s’il existe $c \in A$ tel que $b = a c$ .
On dit que $a$ et $b$ sont associés, noté $a \sim b$ si $a ∣ b$ et si $b ∣ a$ .

Remarque 2. Soient $a, b \in A$ .

$a ∣ b ⟺ (b) \subseteq (a)$ .
$a \sim b ⟺ (b) = (a)$ . Ainsi, $\sim$ est une relation d’équivalence sur $A$ .

Proposition 3. Soient $a, b \in A$ . Alors, $a \sim b ⟺ \exists u \in A^{\times} tel que b = u a$

Définition 4. Soient $a_{1}, \dots, a_{n} \in A^{*}$ .

$d \in A$ est un plus grand commun diviseur PGCD de $a_{1}, \dots, a_{m}$ si $d$ satisfait les deux propriétés suivantes :
1. $d ∣ a_{i}, \forall i \in [[1, n]]$ .
2. Si $\exists d^{'} \in A$ tel que $d^{'} ∣ a_{i}, \forall i \in [[1, n]]$ , alors $d^{'} ∣ d$ .
$m \in A$ est un plus petit commun multiple PPCM de $a_{1}, \dots, a_{n}$ si $m$ satisfait les deux propriétés suivantes :
1. $a_{i} ∣ m, \forall i \in [[1, n]]$ .
2. Si $\exists m^{'} \in A$ tel que $a_{i} ∣ m^{'}, \forall i \in [[1, n]]$ , alors $m ∣ m^{'}$ .

Remarque 5. Un PGCD (resp. un PPCM), lorsqu’il existe, n’est pas toujours unique. Dans un anneau intègre, deux PGCD (resp. PPCM) sont toujours associés puisqu’ils se divisent l’un l’autre. Dans un anneau intègre, on peut donc noter $d \sim pgcd (a, b)$ (resp. $m \sim pgcd (a, b)$ ) lorsque $d$ est un pgcd (resp. $m$ est un ppcm) de $a$ et de $b$ .

[GOU21]
p. 60

Exemple 6. Soient $K$ un corps commutatif. On pose $P_{n} = X^{n} - 1 \in K [X]$ pour $n \in N^{*}$ . Alors, pour $a, b \in N^{*}$ , le PGCD unitaire de $P_{a}$ et $P_{b}$ est égal à $P_{pgcd (a, b)}$ .

[ULM18]
p. 40

Proposition 7. Soient $a, b \in A^{*}$ . Un élément $c \in A$ est un PPCM de $a$ et $b$ si et seulement si $(a) \cap (b) = (c)$ . En particulier, $a$ et $b$ admettent un PPCM si et seulement si $(a) \cap (b)$ est un idéal principal.

Proposition 8. Soient $a, b \in A^{*}$ . Soit $d \in A$ . Les assertions suivantes sont équivalentes.

$d ∣ a$ , $d ∣ b$ et il existe $u, v \in A$ tels que $d = a u + b v$ .
$d \sim pgcd (a, b)$ et il existe $u, v \in A$ tels que $d = a u + b v$ .
$(d) = (a, b)$ .

Définition 9. Deux éléments $a$ et $b$ de $A$ sont dits premiers entre eux s’ils admettent un PGCD et $pgcd (a, b) \sim 1$ .

Exemple 10. $2$ et $X$ sont premiers entre eux dans $Z [X]$ .

Dans un anneau principal

Dans cette section, $A$ désigne toujours un anneau commutatif unitaire. On le suppose de plus principal.

Existence

Théorème 11 (Décomposition de Bézout). Soient $a_{1}, \dots, a_{n} \in A^{*}$ . Alors :

Il existe $d$ un $pgcd$ de $a_{1}, \dots, a_{n}$ . $d$ est tel que $(d) = (a_{1}, \dots, a_{n})$ . En particulier, $d$ est de la forme $d = b_{1} a_{1} + \dots + b_{n} a_{n}$ avec $\forall i \in [[1, n]], b_{i} \in A$ .
Il existe $m$ un $ppcm$ de $a_{1}, \dots, a_{n}$ . $m$ est tel que $(m) = (a_{1}) \cap \dots \cap (a_{n})$ .

p. 52

Exemple 12. Dans $F_{2} [X]$ : $- X (X^{3} + X^{2} + 1) + (1 + X^{2}) (X^{2} + X + 1) = 1$

Application 13. $\overline{X}^{2} + 1$ est inversible dans $F_{2} [X] / (X^{3} + X^{2} + 1)$ d’inverse $\overline{X}^{2} + X + 1$ .

p. 42

Lemme 14 (Gauss). Soient $a, b, c \in A$ avec $a$ et $b$ premiers entre eux. Alors, $a ∣ b c ⟹ a ∣ c$ et $a ∣ c et b ∣ c ⟹ ab ∣ c$

Dans les anneaux euclidiens

Principalité des anneaux euclidiens

Proposition 15. Un anneau euclidien est principal.

On a donc existence de PGCD et de PPCM dans un tel anneau, mais la structure euclidienne permet de plus de fournir des algorithmes de calculs.

p. 47

Théorème 16. Si $K$ est un corps commutatif, alors $K [X]$ est un anneau euclidien de stathme le degré. De plus, le quotient et le reste sont uniques.

Corollaire 17. Les assertions suivantes sont équivalentes :

$A$ est un corps commutatif.
$A [X]$ est un anneau euclidien.
$A [X]$ est un anneau principal.

Algorithmes de calcul

[ROM21]
p. 264

Lemme 18. On suppose $A$ euclidien de stathme $ν$ . Soient $a, b \in A^{*}$ et $r$ un reste dans la division euclidienne de $a$ par $b$ . À inversible près, on a alors :

Si $r = 0$ : $pgcd (a, b) = b$ .
Sinon : $pgcd (a, b) = pgcd (b, r)$ .

Théorème 19 (Algorithme d’Euclide). On suppose $A$ euclidien de stathme $ν$ . Soient $a, b \in A^{*}$ tels que $ν (a) \geq ν (b)$ . On définit une suite $(r_{k})$ décroissante (au sens du stathme) par :

$r_{k} = b$ ;
$r_{1}$ est un reste dans la division euclidienne de $a$ par $b$ , on a donc $r_{1} = 0$ ou $0 \leq ν (r_{1}) < ν (r_{0})$ ;
pour $k \geq 2$ , si $r_{k - 1} = 0$ , alors $r_{k} = 0$ , sinon $r_{k}$ est un reste dans la division euclidienne de $r_{k - 2}$ par $r_{k - 1}$ et on a $r_{k} = 0$ ou $0 \leq ν (r_{k}) < ν (r_{k - 1})$ .

$pgcd (a, b)$ est alors le dernier reste non nul dans cette suite de divisions euclidiennes, que l’on note $r_{n - 1}$ .

Remarque 20. On peut remonter l’algorithme d’Euclide pour obtenir les coefficients de Bézout. On parle alors d’algorithme d’Euclide étendu.

[ULM18]
p. 44

Au lieu de faire les calculs en deux temps (descente, puis remontée), on peut tout faire en même temps via l’algorithme suivant.

Proposition 21 (Algorithme d’Euclide généralisé). En reprenant les notations du Théorème 19 :

Étape 0 : On écrit $r_{0} = a = u_{0} \times a + v_{0} \times b$ avec $(u_{0}, v_{0}) = (1, 0)$ .
Étape 1 : On écrit $r_{1} = b = u_{1} \times a + v_{1} \times b$ avec $(u_{1}, v_{1}) = (0, 1)$ .
Étape 2 : On écrit $r_{0} - q_{1} r_{1} = r_{2} = u_{2} \times a + v_{2} \times b$ avec $(u_{2}, v_{2}) = (1, - q_{1})$ .
…
Étape $k$ : On écrit $r_{k - 1} - q_{k} r_{k} = r_{k + 1} = u_{k + 1} \times a + v_{k + 1} \times b$ .
…
Étape $n - 1$ : On écrit $r_{n - 2} - q_{n - 1} r_{n - 1} = r_{n} = u_{n} \times a + v_{n} \times b$ .
Étape $n$ : On écrit $r_{n - 1} - q_{n} r_{n} = 0 = u_{n + 1} \times a + v_{n + 1} \times b$ .

À la fin, on obtient $pgcd (a, b) = r_{n} = u_{n} a + v_{n} b$ .

Exemple 22. Calculons le PGCD et les coefficients de Bézout de $1763$ et $731$ dans $Z$ .

				$1763$	=	$1$	$1763$	+	$0$	$731$
				$731$	=	$0$	$1763$	+	$1$	$731$
Il y va	$2$	fois	reste	$301$	=	$1$	$1763$	+	$(- 2)$	$731$
	$2$	fois	reste	$129$	=	$(- 2)$	$1763$	+	$5$	$731$
	$2$	fois	reste	$43$	=	$5$	$1763$	+	$(- 12)$	$731$
	$3$	fois	reste	$0$	=	$(- 17)$	$1763$	+	$41$	$731$

On a $pgcd (1763, 731) = 43 = 5 \times 1763 - 12 \times 731$ .

[FFN]
p. 23

Proposition 23. En reprenant les notations précédentes, on a $\forall k \in [[0, n - 1]], r_{k} \geq (\frac{1 + 5}{2})^{n - k}$

Corollaire 24. En reprenant les notations précédentes, cet algorithme a une complexité en $O (ln (a) \times ln (b))$ .

Dans un anneau factoriel

[PER]
p. 48

Proposition 25. Si $A$ vérifie la relation $(*)$ de la Proposition 26, alors les assertions suivantes sont équivalentes :

$A$ vérifie le lemme d’Euclide : si $p \in A$ est irréductible, alors $p ∣ ab ⟹ p ∣ a ou p ∣ b$ .
Pour tout $p \in A$ , $p$ est irréductible si et seulement si $(p)$ premier.
$A$ vérifie le lemme de Gauss : si $p \in A$ est irréductible, alors $a ∣ b c ⟹ a ∣ c$ pour tout $a, b, c \in A$ avec $a$ et $b$ premiers entre eux.

[ULM18]
p. 65

Proposition 26. On suppose $A$ factoriel. Tout élément $a \neq = 0$ peut s’écrire de manière unique $a = u_{a} p \in S \prod p^{v_{p} (a)} (*)$ où $S$ est un système de représentants d’éléments premiers de $A$ (pour le relation $\sim$ ), $u_{a}$ est inversible et $v_{p} (a) \in N$ tous nuls sauf un nombre fini.

Exemple 27. Dans l’anneau principal (donc factoriel, voir Théorème 29) $Z$ , un choix standard pour $S$ est l’ensemble des nombres premiers positifs.

Proposition 28. On suppose $A$ factoriel. Soient $a, b \in A^{*}$ . Alors, en reprenant les notations précédentes :

$a ∣ b ⟺ v_{p} (a) \leq v_{p} (b)$ pour tout $p \in S$ .
$\prod_{p \in S} p^{m i n (v_{p} (a), v_{p} (b))}$ est un PGCD de $a$ et de $b$ .
$\prod_{p \in S} p^{m a x (v_{p} (a), v_{p} (b))}$ est un PPCM de $a$ et de $b$ .

Théorème 29. Tout anneau principal est factoriel.

Contre-exemple 30. $Z [i 5]$ est principal mais n’est pas factoriel.

[GOZ]
p. 10

Lemme 31 (Gauss). On suppose $A$ factoriel. Alors :

Le produit de deux polynômes primitifs est primitif (ie. dont le PGCD des coefficients est associé à $1$ ).
$\forall P, Q \in A [X] ∖ {0}$ , $γ (PQ) = γ (P) γ (Q)$ (où $γ (P)$ est le contenu du polynôme $P$ ).

critere-d-eisenstein

Théorème 32 (Critère d’Eisenstein). Soient $K$ le corps des fractions de $A$ et $P = \sum_{i = 0}^{n} a_{i} X^{i} \in A [X]$ de degré $n \geq 1$ . On suppose que $A$ est factoriel et qu’il existe $p \in A$ irréductible tel que :

$p ∣ a_{i}$ , $\forall i \in [[0, n - 1]]$ .
$p ∤ a_{n}$ .
$p^{2} ∤ a_{0}$ .

Alors $P$ est irréductible dans $K [X]$ .

[PER]
p. 67

Application 33. Soit $n \in N^{*}$ . Il existe des polynômes irréductibles de degré $n$ sur $Z$ .

Applications

En algèbre linéaire

Soit $E$ un espace vectoriel de dimension finie $n$ sur un corps $K$ . Soit $f : E \to E$ un endomorphisme de $E$ .

[GOU21]
p. 186

Proposition 34. Il existe un unique polynôme de $K [X]$ unitaire qui engendre l’idéal ${P \in K [X] ∣ P (f) = 0}$ : c’est le polynôme minimal de $f$ , noté $π_{f}$ . Il s’agit du polynôme unitaire de plus bas degré annulant $f$ . Il divise tous les autres polynômes annulateurs de $f$ .

Théorème 35 (Lemme des noyaux). Soit $P = P_{1} \dots P_{k} \in K [X]$ où les polynômes $P_{1}, \dots, P_{k}$ sont premiers entre eux deux à deux. Alors, $Ker (P (f)) = i = 1 ⨁ k Ker (P_{i} (f))$

Application 36. $f$ est diagonalisable si et seulement si $π_{f}$ est scindé à racines simples.

Systèmes de congruences

[ROM21]
p. 289

Proposition 37. Soit $a$ un entier non nul. L’équation $a x \equiv 1 mod n$ admet des solutions si et seulement si $pgcd (a, n) = 1$ .

Corollaire 38. Soient $a$ un entier non nul et $b$ un entier relatif. L’équation $a x \equiv b mod n$ a des solutions si et seulement si $d = pgcd (a, n) ∣ b$ . Dans ce cas, l’ensemble des solutions est ${\frac{b}{d} x_{0} + k \frac{n}{d} ∣ k \in Z}$ où $x_{0}$ est une solution de l’équation $\frac{a}{n} x \equiv 1 mod n$ .

p. 285

theoreme-chinois

Théorème 39 (Chinois). Soient $n_{1}, \dots, n_{r} \geq 2$ des entiers. On note $n = \prod_{i = 1}^{r} n_{i}$ et $π_{k} = π_{n_{k} Z}$ la surjection canonique de $Z$ sur $Z / k Z$ pour tout $k \in [[1, r]]$ .

Les entiers $n_{1}, \dots, n_{r}$ sont premiers entre eux si et seulement si les anneaux $Z / n Z$ et $\prod_{i = 1}^{r} Z / n_{i} Z$ sont isomorphes. Dans ce cas, l’isomorphisme est explicité par l’application $ψ : Z / n Z π_{n} k \to \mapsto \prod_{i = 1}^{r} Z / n_{i} Z (π_{i} (k))_{i \in [[1, r]]}$

p. 291

Exemple 40. $⎩ ⎨ ⎧ k \equiv 2 mod 4 k \equiv 3 mod 5 k \equiv 1 mod 9$ admet pour ensemble de solutions ${838 + 180 q ∣ q \in Z}$ .