IMG_5432BC1E-53FB-4D88-AD91-251B0927D736.jpeg

# Préparation à l'agrégation de Mathématiques ## PGCD et Bézout ### Définition Soient $a, b \in \mathbb{Z}$. On dit que $d \in \mathbb{N}$ est le PGCD de $a$ et $b$ si : * $d \mid a$ et $d \mid b$ * $\forall d' \in \mathbb{N}$, si $d' \mid a$ et $d' \mid b$ alors $d' \mid d$. ### Théorème d...

# Préparation à l'agrégation de Mathématiques ## PGCD et Bézout ### Définition Soient $a, b \in \mathbb{Z}$. On dit que $d \in \mathbb{N}$ est le PGCD de $a$ et $b$ si : * $d \mid a$ et $d \mid b$ * $\forall d' \in \mathbb{N}$, si $d' \mid a$ et $d' \mid b$ alors $d' \mid d$. ### Théorème de Bézout Soient $a, b \in \mathbb{Z}$. Alors il existe $u, v \in \mathbb{Z}$ tels que $au + bv = pgcd(a, b)$. **Démonstration** Considérons l'ensemble $E = \{au + bv, (u, v) \in \mathbb{Z}^2\} \cap \mathbb{N}$. $E$ est non vide car $|a| \in E$ (prendre $u = \pm 1$ et $v = 0$). Soit $d$ le plus petit élément de $E$. Alors, il existe $u_0, v_0 \in \mathbb{Z}$ tels que $d = au_0 + bv_0$. Effectuons la division euclidienne de $a$ par $d$ : $a = dq + r$ avec $0 \le r < d$ $r = a - dq = a - (au_0 + bv_0)q = a(1 - u_0q) + b(-v_0q)$. Donc $r \in E$, or $r < d$ et $d$ est le plus petit élément de $E$, donc $r = 0$. Donc $d \mid a$. De même, $d \mid b$. Soit $d'$ un diviseur commun de $a$ et $b$. Alors $d' \mid au_0 + bv_0$, donc $d' \mid d$. ### Corollaire Si $a$ et $b$ sont premiers entre eux, alors il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. ### Lemme de Gauss Si $a \mid bc$ et $a \land b = 1$, alors $a \mid c$. **Démonstration** $a \mid bc$ donc il existe $k \in \mathbb{Z}$ tel que $bc = ak$. $a \land b = 1$ donc il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. $cau + cbv = c$ $cau + akv = c$ $a(cu + kv) = c$ Donc $a \mid c$. ### Théorème Si $p$ est premier et $p \mid ab$, alors $p \mid a$ ou $p \mid b$. **Démonstration** Si $p \mid a$, c'est bon. Sinon, $p$ et $a$ sont premiers entre eux. $p \mid ab$ et $p \land a = 1$, donc d'après le lemme de Gauss, $p \mid b$. ### Corollaire Si $p$ est premier et $p \mid a_1 \dots a_n$, alors il existe $i \in \{1, \dots, n\}$ tel que $p \mid a_i$.