Mathématiques expertes (option) · Terminale

PGCD et algorithme d'Euclide : exercices corrigés de Terminale

Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur

L'essentiel

Pour calculer PGCD(a, b), on remplace le couple (a, b) par (b, reste de la division de a par b) jusqu'à obtenir un reste nul ³.
Le PGCD est le dernier reste non nul ³.
On utilise PGCD(a, 0) = a et PGCD(a, b) = PGCD(b, a mod b) ³.
L'algorithme étendu fournit aussi des entiers u et v tels que au + bv = PGCD(a, b) ⁴.
Quand a et b sont premiers entre eux, u est l'inverse de a modulo b ⁴.

Comment utiliser ces exercices

Ces exercices partent du calcul direct d'un PGCD et vont jusqu'à la recherche de coefficients de Bézout, puis à la résolution d'une équation à deux inconnues entières. Cherche d'abord seul(e) sur ta feuille. Si tu bloques, ouvre un indice, puis reprends ton calcul. Compare enfin avec la correction : chaque étape y correspond à une action précise, refais-la de ton côté avant de lire la suivante.

Les niveaux 1 sont des applications directes de la méthode. Les niveaux 2 demandent de traduire un problème concret ou de mener des calculs plus longs sans faute. Les niveaux 3 mobilisent l'algorithme étendu et le lien avec les congruences, que tu as vues juste avant ce chapitre.

MéthodePrésenter un calcul proprement

Écris chaque division sous la forme $a = b \times q + r$ avec $0 \le r < b$ , une ligne par division. La dernière ligne a un reste nul ; le reste de la ligne précédente est le PGCD. Pour les coefficients de Bézout, l'algorithme étendu calcule en plus deux entiers $u$ et $v$ tels que $au + bv = \text{PGCD}(a, b)$ ⁴ : on peut les obtenir en remontant les divisions, comme dans les derniers exercices.

Pour remonter, procède toujours dans le même ordre : isole le dernier reste non nul dans la division qui le produit, puis remplace chaque reste intermédiaire par son expression en fonction des deux nombres qui le précèdent. Ne développe pas trop tôt : garde les nombres de départ (ici 120, 23, etc.) sous forme de symboles à regrouper à la fin.

Après les exercices

Si tu as réussi les derniers exercices, tu es prêt(e) pour le théorème de Bézout, qui explique pourquoi une telle combinaison existe toujours, puis pour le théorème de Gauss, qui s'appuie sur elle. L'algorithme étendu est l'outil qui rend ces théorèmes calculables ⁴.

Les exercices

Exercice 1 Un premier calcul de PGCD

★☆☆Environ 5 min

Calcule $\text{PGCD}(252, 198)$ avec l'algorithme d'Euclide. Écris toutes les divisions euclidiennes.

Indice 1

Commence par diviser 252 par 198 et note le reste.

Indice 2

À chaque étape, le diviseur devient dividende et le reste devient diviseur.

Voir la correction pas à pas

Première division : $252 = 198 \times 1 + 54$ . Le reste est 54.
On remplace le couple $(252, 198)$ par $(198, 54)$ ³. Deuxième division : $198 = 54 \times 3 + 36$ .
Nouveau couple $(54, 36)$ : $54 = 36 \times 1 + 18$ .
Nouveau couple $(36, 18)$ : $36 = 18 \times 2 + 0$ . Le reste est nul, l'algorithme s'arrête.
Le dernier reste non nul est 18 ³.

$\text{PGCD}(252, 198) = 18$ . Vérification rapide : $252 = 18 \times 14$ et $198 = 18 \times 11$ , et 14 et 11 n'ont pas de diviseur commun autre que 1.

Exercice 2 Des divisions à la chaîne

★☆☆Environ 6 min

Calcule $\text{PGCD}(1071, 462)$ en détaillant les divisions euclidiennes successives.

Indice 1

$462 \times 2 = 924$ : le premier reste se calcule vite.

Indice 2

Pense à vérifier que chaque reste est plus petit que le diviseur.

Voir la correction pas à pas

$1071 = 462 \times 2 + 147$ : le reste est 147.
On passe au couple $(462, 147)$ : $462 = 147 \times 3 + 21$ .
On passe au couple $(147, 21)$ : $147 = 21 \times 7 + 0$ .
Le reste est nul. Le dernier reste non nul est 21 ³.

$\text{PGCD}(1071, 462) = 21$ . Cela signifie que 21 est le plus grand entier qui divise à la fois 1071 et 462 ³.

Exercice 3 Rendre une fraction irréductible

★☆☆Environ 8 min

On considère la fraction $\dfrac{693}{1155}$ .

Calcule $\text{PGCD}(1155, 693)$ .
Écris la fraction sous forme irréductible. Donne son dénominateur.

Indice 1

Une fraction est irréductible quand on a divisé numérateur et dénominateur par leur PGCD.

Indice 2

Commence par $1155 = 693 \times 1 + \dots$

Voir la correction pas à pas

$1155 = 693 \times 1 + 462$ .
$693 = 462 \times 1 + 231$ .
$462 = 231 \times 2 + 0$ . Le dernier reste non nul est 231, donc $\text{PGCD}(1155, 693) = 231$ ³.
On divise numérateur et dénominateur par 231 : $693 = 231 \times 3$ et $1155 = 231 \times 5$ .
La fraction irréductible est $\dfrac{3}{5}$ , de dénominateur 5.

$\dfrac{693}{1155} = \dfrac{3}{5}$ . Le calcul du PGCD évite de simplifier par étapes successives sans être sûr d'avoir fini.

Exercice 4 Carreler un rectangle

★★☆Environ 12 min

Un sol rectangulaire mesure 1680 cm sur 924 cm. On veut le recouvrir entièrement avec des carreaux carrés tous identiques, sans les couper, en choisissant des carreaux les plus grands possible.

Quelle est la longueur du côté d'un carreau ?
Combien de carreaux faut-il ? Donne ce nombre.

Indice 1

Le côté d'un carreau doit diviser 1680 et 924.

Indice 2

Dans la tradition grecque, le PGCD de deux longueurs est le côté du plus grand carré qui carrelle le rectangle ³.

Voir la correction pas à pas

Le côté $c$ doit être un diviseur commun de 1680 et 924 ; le plus grand possible est leur PGCD ³.
$1680 = 924 \times 1 + 756$ .
$924 = 756 \times 1 + 168$ .
$756 = 168 \times 4 + 84$ .
$168 = 84 \times 2 + 0$ . Donc $c = 84$ cm.
Nombre de carreaux dans la longueur : $1680 \div 84 = 20$ . Dans la largeur : $924 \div 84 = 11$ .
Total : $20 \times 11 = 220$ carreaux.

Les carreaux ont 84 cm de côté et il en faut 220. Un carreau plus petit conviendrait aussi s'il a pour côté un diviseur de 84, mais il en faudrait davantage.

Exercice 5 Des nombres plus grands

★★☆Environ 12 min

Calcule $\text{PGCD}(123456, 7890)$ . Les restes successifs sont à calculer avec soin ; vérifie chacun avec une multiplication.

Indice 1

$7890 \times 15 = 118350$ .

Indice 2

Le deuxième reste est 2784 : pense à soustraire 5106 de 7890.

Voir la correction pas à pas

$123456 = 7890 \times 15 + 5106$ .
$7890 = 5106 \times 1 + 2784$ .
$5106 = 2784 \times 1 + 2322$ .
$2784 = 2322 \times 1 + 462$ .
$2322 = 462 \times 5 + 12$ (car $462 \times 5 = 2310$ ).
$462 = 12 \times 38 + 6$ (car $12 \times 38 = 456$ ).
$12 = 6 \times 2 + 0$ . Le dernier reste non nul est 6 ³.

$\text{PGCD}(123456, 7890) = 6$ . À chaque étape, les nombres considérés diminuent, ce qui garantit que le calcul finit ³.

Exercice 6 Deux termes consécutifs de la suite de Fibonacci

★★☆Environ 10 min

Calcule $\text{PGCD}(144, 89)$ . Observe la forme des quotients obtenus et dis ce que tu remarques.

Indice 1

Le premier quotient est 1 et le premier reste est 55.

Indice 2

Tous les quotients sauf le dernier sont égaux.

Voir la correction pas à pas

$144 = 89 \times 1 + 55$ .
$89 = 55 \times 1 + 34$ .
$55 = 34 \times 1 + 21$ .
$34 = 21 \times 1 + 13$ .
$21 = 13 \times 1 + 8$ , puis $13 = 8 \times 1 + 5$ , puis $8 = 5 \times 1 + 3$ .
$5 = 3 \times 1 + 2$ , puis $3 = 2 \times 1 + 1$ .
$2 = 1 \times 2 + 0$ . Le dernier reste non nul est 1 ³.

$\text{PGCD}(144, 89) = 1$ : les deux nombres sont premiers entre eux. Tous les quotients valent 1 sauf le dernier. Les restes successifs redescendent la suite 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1 : les nombres ne diminuent que lentement à chaque étape, ce qui allonge le calcul pour des nombres de cette taille.

Exercice 7 Un coefficient de Bézout et un inverse modulaire

★★★Environ 15 min

Calcule $\text{PGCD}(120, 23)$ .
En remontant les divisions, trouve deux entiers $u$ et $v$ tels que $120u + 23v = 1$ .
En déduire l'inverse de 23 modulo 120, c'est-à-dire l'entier $x$ de $\{0, \dots, 119\}$ tel que $23x \equiv 1 \pmod{120}$ . Donne $x$ .

Indice 1

Écris d'abord toutes les divisions jusqu'au reste nul.

Indice 2

Pour remonter, exprime 1 à partir des deux derniers restes, puis remplace chaque reste par son expression.

Voir la correction pas à pas

Divisions : $120 = 23 \times 5 + 5$ , puis $23 = 5 \times 4 + 3$ , puis $5 = 3 \times 1 + 2$ , puis $3 = 2 \times 1 + 1$ , puis $2 = 1 \times 2 + 0$ . Le PGCD vaut 1.
On exprime 1 : $1 = 3 - 2$ .
On remplace $2 = 5 - 3$ : $1 = 3 - (5 - 3) = 2 \times 3 - 5$ .
On remplace $3 = 23 - 4 \times 5$ : $1 = 2 \times 23 - 9 \times 5$ .
On remplace $5 = 120 - 5 \times 23$ : $1 = 2 \times 23 - 9 \times 120 + 45 \times 23 = 47 \times 23 - 9 \times 120$ .
Donc $u = -9$ et $v = 47$ . Contrôle : $120 \times (-9) + 23 \times 47 = -1080 + 1081 = 1$ .
Les nombres étant premiers entre eux, le coefficient de 23 est l'inverse de 23 modulo 120 ⁴. Comme $47 \in \{0, \dots, 119\}$ , on a $x = 47$ .

$\text{PGCD}(120, 23) = 1$ et $120 \times (-9) + 23 \times 47 = 1$ . L'inverse de 23 modulo 120 est 47. Vérification : $23 \times 47 = 1081 = 9 \times 120 + 1$ .

Exercice 8 Remonter l'algorithme pour 252 et 198

★★★Environ 15 min

On reprend les nombres du premier exercice.

Écris le PGCD de 252 et 198 comme une combinaison $252u + 198v$ avec $u$ et $v$ entiers.
Vérifie ton résultat par un calcul numérique.
Explique pourquoi le couple $(u, v)$ n'est pas unique.

Indice 1

Utilise les divisions : $54 = 252 - 198$ et $36 = 198 - 3 \times 54$ .

Indice 2

Pour la question 3, ajoute à $u$ un multiple de 198 et retire le multiple correspondant de 252 à $v$ .

Voir la correction pas à pas

Les divisions du premier exercice donnent : $54 = 252 - 198$ et $36 = 198 - 3 \times 54$ et $18 = 54 - 36$ .
On remplace 36 : $18 = 54 - (198 - 3 \times 54) = 4 \times 54 - 198$ .
On remplace 54 : $18 = 4 \times (252 - 198) - 198 = 4 \times 252 - 5 \times 198$ .
On obtient $u = 4$ et $v = -5$ . Contrôle : $4 \times 252 = 1008$ , $5 \times 198 = 990$ , et $1008 - 990 = 18$ .
Pour l'unicité : $252 \times 198 - 198 \times 252 = 0$ . Donc $(4 + 198, -5 - 252)$ convient aussi, puisqu'on ajoute 0 au résultat.

$18 = 252 \times 4 + 198 \times (-5)$ . L'algorithme étendu fournit un couple de coefficients de Bézout ⁴, mais il en existe une infinité : on dit « un » couple et non « le » couple.

Exercice 9 Une équation à deux inconnues entières

★★★Environ 15 min

On cherche des entiers $x$ et $y$ tels que $120x + 23y = 3$ .

À partir de l'égalité $120 \times (-9) + 23 \times 47 = 1$ , déduis une solution $(x, y)$ .
Vérifie-la par un calcul.
Donne la valeur de $y$ trouvée.

Indice 1

Multiplie les deux membres de l'égalité de départ par 3.

Indice 2

Le membre de droite doit devenir 3.

Voir la correction pas à pas

On part de $120 \times (-9) + 23 \times 47 = 1$ .
On multiplie chaque terme par 3 : $120 \times (-27) + 23 \times 141 = 3$ .
On lit une solution : $x = -27$ et $y = 141$ .
Contrôle : $120 \times (-27) = -3240$ et $23 \times 141 = 3243$ , et $-3240 + 3243 = 3$ .
Donc $y = 141$ .

Le couple $(-27, 141)$ est une solution de $120x + 23y = 3$ . Cette méthode fonctionne parce que le PGCD de 120 et 23 vaut 1 : une identité de Bézout pour 1 se multiplie par n'importe quel entier ⁴. Ce n'est pas la seule solution possible, comme dans l'exercice précédent.

Les questions qu'on se pose

Pourquoi l'algorithme d'Euclide s'arrête-t-il toujours ?

À chaque étape, on calcule le reste d'une division euclidienne par $b$ : ce reste est supérieur ou égal à 0 et strictement inférieur à $b$ ³. La suite des restes est donc une suite d'entiers positifs strictement décroissante ; elle ne peut pas descendre indéfiniment et atteint 0 au bout d'un nombre fini d'étapes ³.

Dois-je diviser le plus grand par le plus petit, ou peut-on commencer dans l'autre sens ?

On divise le plus grand par le plus petit ³. Si tu fais l'inverse, la première division donne un quotient 0 et un reste égal au plus petit nombre : tu perds une ligne mais le résultat reste correct, car le couple est simplement échangé.

À quoi servent les coefficients u et v ?

L'algorithme d'Euclide étendu donne deux entiers $u$ et $v$ tels que $au + bv = \text{PGCD}(a, b)$ ⁴. Quand $a$ et $b$ sont premiers entre eux, $u$ est un inverse de $a$ modulo $b$ ⁴. C'est utile pour résoudre des congruences et des équations à deux inconnues entières, ce que tu retrouveras avec le théorème de Bézout.

Sources

Arithmétique — Ressources d'accompagnement Mathématiques expertes, Éduscol — Ministère de l'Éducation nationale. Consulté le 6 novembre 2026.
EduPython — Documentation enseignant (Algorithme d'Euclide), Académie d'Aix-Marseille. Consulté le 6 novembre 2026.
Algorithme d'Euclide, Wikipédia. Consulté le 6 novembre 2026.
Algorithme d'Euclide étendu, Wikipédia. Consulté le 6 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

PGCD et algorithme d'Euclide : exercices corrigés de Terminale

L'essentiel

Comment utiliser ces exercices

Après les exercices

Les exercices

Exercice 1 Un premier calcul de PGCD

Exercice 2 Des divisions à la chaîne

Exercice 3 Rendre une fraction irréductible

Exercice 4 Carreler un rectangle

Exercice 5 Des nombres plus grands

Exercice 6 Deux termes consécutifs de la suite de Fibonacci

Exercice 7 Un coefficient de Bézout et un inverse modulaire

Exercice 8 Remonter l'algorithme pour 252 et 198

Exercice 9 Une équation à deux inconnues entières

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur