PGCD, théorèmes de Bézout et de Gauss
Plus grand commun diviseur et algorithme d'Euclide, nombres premiers entre eux, théorème et identité de Bézout, théorème de Gauss et ses corollaires, équations diophantiennes ax + by = c.
1. PGCD et algorithme d'Euclide
Définition · PGCD
Le PGCD de deux entiers non tous deux nuls est le plus grand entier naturel qui les divise tous les deux. Deux entiers sont premiers entre eux si leur PGCD vaut $1$.
Propriété · Algorithme d'Euclide
Si $a = bq + r$, alors $\mathrm{PGCD}(a\,;\,b) = \mathrm{PGCD}(b\,;\,r)$. On répète les divisions euclidiennes : le PGCD est le dernier reste non nul.
Exemple · PGCD(252 ; 198)
$252 = 198 \times 1 + 54$ ; $198 = 54 \times 3 + 36$ ; $54 = 36 \times 1 + 18$ ; $36 = 18 \times 2 + 0$. Donc $\mathrm{PGCD}(252\,;\,198) = 18$.
2. Théorème de Bézout
Propriété · Identité et théorème de Bézout
Il existe des entiers $u$ et $v$ tels que $au + bv = \mathrm{PGCD}(a\,;\,b)$.
Théorème de Bézout : $a$ et $b$ sont premiers entre eux $\iff$ il existe des entiers $u$, $v$ tels que $au + bv = 1$.
Méthode · Trouver u et v
On « remonte » l'algorithme d'Euclide. Pour $35$ et $24$ : $35 = 24 + 11$, $24 = 2 \times 11 + 2$, $11 = 5 \times 2 + 1$. Donc $1 = 11 - 5 \times 2 = 11 - 5(24 - 2 \times 11) = 11 \times 11 - 5 \times 24 = 11(35 - 24) - 5 \times 24 = 35 \times 11 - 24 \times 16$.
3. Théorème de Gauss
Propriété · Théorème de Gauss
Si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.
Corollaire : si $a$ et $b$ divisent $n$ et sont premiers entre eux, alors $ab$ divise $n$.
4. Équations ax + by = c
Méthode · Résolution
L'équation $ax + by = c$ a des solutions entières si et seulement si $\mathrm{PGCD}(a\,;\,b)$ divise $c$. On trouve une solution particulière $(x_0\,;\,y_0)$ (Bézout), on soustrait, puis on applique le théorème de Gauss.
Exemple · 3x + 5y = 1
$(2\,;\,-1)$ est solution. Alors $3(x - 2) = -5(y + 1)$ ; $5$ divise $3(x - 2)$ et est premier avec $3$, donc $5 \mid x - 2$ : $x = 2 + 5k$ et $y = -1 - 3k$, $k \in \mathbb{Z}$.
Attention · PGCD et PPCM
Pour des entiers naturels non nuls : $\mathrm{PGCD}(a\,;\,b) \times \mathrm{PPCM}(a\,;\,b) = ab$.
S'entraîner
Exercices corrigés
🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.
Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.
PGCD(252 ; 198)
★☆☆Calculer $\mathrm{PGCD}(252\,;\,198)$ avec l'algorithme d'Euclide.
PGCD(1071 ; 462)
★★☆Calculer $\mathrm{PGCD}(1071\,;\,462)$.
Coefficients de Bézout
★★☆Montrer que $35$ et $24$ sont premiers entre eux et trouver $u$, $v$ tels que $35u + 24v = 1$.
17u + 5v = 1
★☆☆Trouver une solution entière de $17u + 5v = 1$.
n et n + 1
★☆☆Montrer que deux entiers consécutifs sont premiers entre eux.
2n + 1 et 3n + 2
★★☆Montrer que $2n + 1$ et $3n + 2$ sont premiers entre eux pour tout entier $n$.
Application de Gauss
★☆☆$x$ est un entier tel que $7$ divise $4x$. Montrer que $7$ divise $x$.
5x = 3y
★★☆Résoudre $5x = 3y$ dans $\mathbb{Z}^2$.
3x + 5y = 1
★★☆Résoudre $3x + 5y = 1$ dans $\mathbb{Z}^2$.
Pas de solution
★☆☆L'équation $14x - 21y = 5$ a-t-elle des solutions entières ?
7x + 12y = 3
★★★Résoudre $7x + 12y = 3$ dans $\mathbb{Z}^2$.
Poules et lapins
★★★Un fermier dépense exactement $100$ € en achetant des poules à $7$ € et des lapins à $12$ €. Combien de chaque ?
PGCD × PPCM
★☆☆Vérifier la relation $\mathrm{PGCD} \times \mathrm{PPCM} = ab$ pour $a = 12$ et $b = 18$.
Fraction irréductible
★☆☆Rendre irréductible $\dfrac{252}{198}$.
Inverse modulo 26
★★☆Trouver un inverse de $7$ modulo $26$.
7x ? 3 [26]
★★☆Résoudre $7x \equiv 3\ [26]$.
Euclide en Python
★★☆Écrire une fonction Python pgcd(a, b) utilisant l'algorithme d'Euclide.
Corollaire de Gauss
★★☆Un entier $n$ est divisible par $4$ et par $9$. Montrer qu'il est divisible par $36$.
PGCD(a ; a + b)
★★★Montrer que si $a$ et $b$ sont premiers entre eux, alors $a$ et $a + b$ le sont aussi.
Engrenages
★★☆Deux roues dentées de $24$ et $36$ dents engrènent. Au bout de combien de tours de chaque roue reviennent-elles pour la première fois à la position de départ ?
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.