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 ppcm (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ézoutSoient $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

Lemme de GaussSoient $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’EuclideOn 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 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 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$ non nul et non inversible, $p$ est irréductible si et seulement si $(p)$ est premier.
$A$ vérifie le lemme de Gauss : pour tout $a, b, c \in A$ tels que $a$ et $b$ sont premiers entre eux, $a ∣ b c ⟹ a ∣ c$ .

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

Lemme de GaussOn 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}$ , $γ (P Q) = γ (P) γ (Q)$ (où $γ (P)$ est le contenu du polynôme $P$ ).

critere-d-eisenstein

Théorème 32

Critère d’EisensteinSoient $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 noyauxSoit $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}{d} x \equiv 1 mod \frac{n}{d}$ .

p. 285

theoreme-chinois

Théorème 39

Théorème chinoisSoient $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 / n_{k} Z$ pour tout $k \in [[1, r]]$ .

Les entiers $n_{1}, \dots, n_{r}$ sont premiers entre eux deux à deux 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}$ .