Prépa, 1re année › Arithmétique dans $\mathbb{Z}$ › Lemme d'Euclide (version algorithmique)
Lemme d'Euclide (version algorithmique) : énoncé (MPSI)
Propriété
Lemme d'Euclide (version algorithmique)
Soient $a, b, q, r \in \mathbb{Z}$ tels que $a = bq + r$. Alors $a$ et $b$ ont les mêmes diviseurs communs que $b$ et $r$ : $$\mathcal{D}(a) \cap \mathcal{D}(b) = \mathcal{D}(b) \cap \mathcal{D}(r).$$ En particulier, si $(a, b) \neq (0,0)$, alors $a \wedge b = b \wedge r$.
Démonstration : Lemme d'Euclide (version algorithmique)
Démonstration
Preuve du lemme
Si $c$ divise $a$ et $b$, alors $c$ divise $a - qb = r$, donc $c$ divise $b$ et $r$.
Si $c$ divise $b$ et $r$, alors $c$ divise $bq + r = a$, donc $c$ divise $a$ et $b$.
Les deux ensembles sont égaux, donc ils ont le même plus grand élément.
S’entraîner
- PGCD, coefficients de Bézout et PPCM de 4199 et 1729
- Expressions premières entre elles
- Équation diophantienne $323x + 391y = c$
- PGCD de deux nombres de la forme $2^k - 1$
- Un principe de chiffrement à clé publique (type CCINP)
Dans le cours
Arithmétique dans $\mathbb{Z}$ : Lemme d'Euclide (version algorithmique)