Exo 1 · Facile Calculer
Calcule PGCD(60 ; 84) avec l'algorithme d'Euclide.
PGCD, théorèmes de Bézout et de Gauss
Terminale — option · Nombres et calculs · BO 2019 (Maths expertes)
PGCD et algorithme d'Euclide, nombres premiers entre eux, théorèmes de Bézout et de Gauss, équations diophantiennes.
Étape 01 / 07
Avant de commencer
Question honnête : où en es-tu ?
Sais-tu calculer le PGCD de 48 et 36 avec l'algorithme d'Euclide ?
Étape 02 / 07
Prérequis
- Divisibilité et division euclidienne (chapitre précédent).
- Congruences modulo n.
- Multiples et diviseurs communs.
- Manipulation d'égalités à coefficients entiers.
Étape 03 / 07
Cours
3.1 — PGCD et algorithme d'Euclide
Le PGCD de a et b est le plus grand diviseur commun. Algorithme d'Euclide : PGCD(a ; b) = PGCD(b ; r) où r est le reste de a par b. On répète jusqu'à un reste nul ; le dernier reste non nul est le PGCD.
3.2 — Nombres premiers entre eux
a et b sont premiers entre eux lorsque PGCD(a ; b) = 1. Toute fraction se simplifie en divisant numérateur et dénominateur par leur PGCD : on obtient une fraction irréductible.
3.3 — Théorème de Bézout
a et b sont premiers entre eux si et seulement s'il existe des entiers u, v tels que au + bv = 1. Plus généralement, il existe u, v avec au + bv = PGCD(a ; b) (identité de Bézout).
3.4 — Théorème de Gauss
Si a divise bc et si a est premier avec b, alors a divise c. Outil central pour résoudre les équations diophantiennes au + bv = c.
Erreur classique
« a | bc ⟹ a | b ou a | c » est faux sans hypothèse de primalité : 6 | (4 × 9) mais 6 ne divise ni 4 ni 9. Gauss exige a premier avec b.
Étape 04 / 07
Exemples résolus
Ex 1 — Euclide
PGCD(48 ; 36) : 48 = 36 × 1 + 12 ; 36 = 12 × 3 + 0. Dernier reste non nul = 12.
Ex 2 — Bézout
7 et 5 premiers entre eux : 7 × 3 + 5 × (−4) = 21 − 20 = 1. Donc (u ; v) = (3 ; −4).
Ex 3 — Gauss
7 divise 5n et 7 premier avec 5 ⟹ 7 divise n.
Ex 4 — Diophantienne
3x + 5y = 1 : une solution particulière est (2 ; −1), les solutions sont x = 2 + 5k, y = −1 − 3k, k ∈ ℤ.
Étape 05 / 07
Exercices d'application
Exo 2 · Facile Calculer
Rends irréductible la fraction de numérateur 105 et de dénominateur 60.
Exo 3 · Moyen Calculer
Détermine un couple (u ; v) tel que 11u + 8v = 1.
Exo 4 · Moyen Raisonner
Montre que deux entiers consécutifs n et n + 1 sont toujours premiers entre eux.
Exo 5 · Moyen Raisonner
Avec le théorème de Gauss, montre que si 5 | 3n alors 5 | n.
Exo 6 · Moyen Modéliser
Résous dans ℤ l'équation 4x + 6y = 2.
Exo 7 · Défi Raisonner
Détermine toutes les solutions entières de 7x + 5y = 3.
Exo 8 · Défi Communiquer
Explique pourquoi le théorème de Gauss nécessite l'hypothèse « a premier avec b » avec un contre-exemple.
Étape 06 / 07
Synthèse — À retenir
- Algorithme d'Euclide : PGCD = dernier reste non nul.
- Premiers entre eux ⟺ PGCD = 1 ⟺ fraction irréductible.
- Bézout : PGCD(a ; b) = 1 ⟺ ∃ u, v, au + bv = 1.
- Gauss : a | bc et a premier avec b ⟹ a | c.
- Résolution des diophantiennes : solution particulière + solution générale.
Étape 07 / 07
Plan de révisions
J+1
Refais exos 1 et 2.
J+7
Refais exos 3 et 6.
J+30
Exos 7 et 8.
Pour aller plus loin
Q1. Pourquoi l'algorithme d'Euclide se termine-t-il toujours ?
Q2. Comment passer d'une solution particulière à toutes les solutions d'une diophantienne ?