Mathématiques expertes (option) · Terminale
PGCD et algorithme d'Euclide : quiz de Terminale expertes
Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur
L'essentiel
- L'algorithme d'Euclide calcule le PGCD de deux entiers par divisions euclidiennes successives. 3
- À chaque étape, on remplace le couple (a, b) par (b, r), où r désigne le reste de la division de a par b : le PGCD reste le même. 3
- On s'arrête au premier reste nul : le PGCD est le dernier reste non nul. 3
- L'algorithme étendu fournit en plus des entiers u et v tels que au + bv = PGCD(a, b). 4
- Si a et b sont premiers entre eux, u est l'inverse de a modulo b. 4
Avant de commencer
Ce quiz couvre tout ce que tu dois maîtriser sur le PGCD et l'algorithme d'Euclide : le principe des divisions successives, la condition d'arrêt, la lecture d'un tableau de calcul, la terminaison, puis la variante étendue qui donne les coefficients de Bézout. Tu as déjà vu la divisibilité, la division euclidienne et les congruences ; elles suffisent pour tout comprendre ici.
Le PGCD de deux entiers est le plus grand entier qui divise les deux. 3 L'algorithme d'Euclide le calcule efficacement, sans avoir besoin de lister tous les diviseurs. 3 Il figure parmi les plus anciens algorithmes connus et reste d'actualité. 3
Quiz
15 questions · correction immédiate · ton score reste sur ton appareil.
-
On remplace le couple par , où est le reste de la division euclidienne de par ; le PGCD ne change pas. 3 Remplacer le reste par le quotient est faux : c'est bien le reste qui fait décroître les nombres. Le produit est un multiple commun des deux nombres, pas leur PGCD.
-
Le quotient de 21 par 15 est 1 et le reste est 6. 3 La proposition ne donne pas 21 : le quotient est trop grand. Diviser 21 par 6 est une étape qui n'a pas lieu au départ, car on divise d'abord par .
-
On divise : , puis , puis . L'algorithme s'arrête au reste nul et renvoie le dernier reste non nul, ici 3. 3 Répondre 0 est l'erreur tentante : 0 est le reste d'arrêt, pas le PGCD. Répondre 6 oublie l'étape suivante, car 6 ne divise pas 15.
-
puis . Le dernier reste non nul est 12. 3 Donner 36 est tentant car 36 est le plus petit des deux nombres, mais 36 ne divise pas 84 ().
-
, puis , puis . Le dernier reste non nul est 21. 3 Un élève qui s'arrête à 42 se trompe : 42 ne divise pas 105. Il faut aller jusqu'au reste nul.
-
, puis , puis . Le dernier reste non nul est 21. 3 Le quotient 7 de la dernière division n'est pas le PGCD : seul le reste intervient dans la réponse.
-
L'algorithme continue avec et le reste précédent, jusqu'à trouver un reste nul ; il retourne alors le dernier reste non nul. 3 Le reste nul n'est pas le PGCD : au moment de l'arrêt, le couple est et PGCD. Le quotient ne joue aucun rôle dans la réponse.
-
On a PGCD(a, 0) = a pour tout entier . 3 Tout entier divise 0, donc le plus grand diviseur commun de 17 et 0 est le plus grand diviseur de 17, soit 17. Répondre 0 est l'erreur tentante : 0 n'est pas un diviseur de 17.
-
Pour non nul, le calcul de PGCD(a, b) fait appel à PGCD(a', b') avec , car est le reste d'une division euclidienne par . 3 Les valeurs de diminuent donc à chaque étape et finissent par atteindre 0. Les quotients ne tendent pas vers 1, et les nombres de départ n'ont aucune raison d'être premiers entre eux.
-
On remplace le plus grand nombre par le reste de la division : le nouveau couple est (diviseur, reste), donc . 3 Le couple inverse l'ordre : la division suivante serait alors celle de 3 par 6, qui donne quotient 0 et reste 3, une étape inutile. Garder 15 ne fait pas diminuer les nombres.
-
Comme , on a PGCD(21, 15) = PGCD(15, 6), et comme , on a PGCD(15, 6) = PGCD(6, 3). 3 Les deux autres sont fausses : le reste de 21 par 15 est 6 et non 1, et le reste de 15 par 6 est 3 et non 2. Il suffit de recalculer le reste pour les écarter.
-
C'est faux. Le PGCD est calculé, mais l'algorithme étendu fournit en plus un couple de coefficients de Bézout, c'est-à-dire deux entiers et tels que . 4 Dire que c'est identique à l'algorithme simple oublie justement cet apport, qui sert à résoudre des équations et à calculer des inverses modulaires.
-
Le dernier reste non nul est 1. 3 Les nombres 120 et 23 sont donc premiers entre eux. Donner 2 revient à s'arrêter une étape trop tôt : 2 est le reste qui précède le dernier reste non nul, et il ne divise pas 23.
-
En réduisant l'égalité modulo 120, on obtient , donc 47 est l'inverse de 23 modulo 120. Lorsque et sont premiers entre eux, est l'inverse de modulo et celui de modulo . 4 Ici , et . Le coefficient serait associé à l'inverse de 120 modulo 23 (à un multiple de 23 près), mais pas 47. Le PGCD vaut 1, et le quotient de 120 par 23 est 5.
-
L'algorithme est décrit dans le livre VII (propositions 1 à 3) des Éléments d'Euclide, vers 300 av. J.-C. 3 Bézout (1766) est associé à l'algorithme étendu, pas à l'algorithme simple. 1 Un mathématicien indien, Aryabhata, a décrit au Ve siècle une version indépendante qu'il appelle le « pulvérisateur », mais ce n'est pas la source la plus ancienne. 3
Les questions qu'on se pose
Pourquoi le PGCD est-il le dernier reste non nul et pas le dernier quotient ?
À chaque étape, PGCD(a, b) = PGCD(b, r), donc le PGCD ne change pas quand on passe d'un couple au suivant. 3 Quand le reste devient nul, le couple est de la forme (d, 0), et PGCD(d, 0) = d. 3 Le nombre est le reste de l'étape précédente, c'est-à-dire le dernier reste non nul. Les quotients servent à écrire les divisions, mais ne figurent jamais dans le résultat.
Dois-je placer le plus grand nombre en premier ?
On commence par diviser le plus grand par le plus petit, c'est la manière naturelle de procéder. Si tu inverses les deux nombres au départ, la première division donne un quotient nul et un reste égal au premier nombre : tu perds simplement une étape, puis le calcul reprend normalement. Le résultat reste correct, mais tu gagnes du temps en classant tes nombres d'abord.
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.