Mathématiques expertes (option) · Terminale

PGCD et algorithme d'Euclide : cours de Terminale (maths expertes)

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

L'essentiel

Le PGCD de deux entiers est leur plus grand diviseur commun. Deux règles suffisent pour le calculer : PGCD(a, 0) = a, et PGCD(a, b) = PGCD(b, r) quand r est le reste de a divisé par b.
Algorithme d'Euclide : on divise, on décale (a prend la valeur de b, b celle du reste), on recommence jusqu'à un reste nul. Le PGCD est le dernier reste non nul.
Il s'arrête toujours : les restes forment une suite d'entiers positifs strictement décroissante.
L'algorithme d'Euclide étendu remonte les divisions et fournit des entiers u et v tels que au + bv = PGCD(a, b) (coefficients de Bézout).
Si le PGCD vaut 1, u est l'inverse de a modulo b : c'est l'outil de base pour résoudre des congruences.

Rappels et définition du PGCD

Au collège, tu as cherché le plus grand diviseur commun de deux nombres en listant leurs diviseurs, ou en simplifiant des fractions. L'algorithme d'Euclide, qui calcule ce PGCD par divisions successives, a longtemps été enseigné en classe de troisième ² ; tu l'as peut-être déjà croisé. En Terminale, avec l'option mathématiques expertes, on change de regard : on ne se contente plus d'appliquer la méthode, on démontre qu'elle s'arrête et qu'elle donne le bon résultat, puis on l'enrichit pour obtenir bien plus qu'un simple PGCD.

Tu as besoin de deux notions vues avant : la divisibilité et la division euclidienne. Voici ce qu'il faut avoir en tête.

La propriété qui fait tout fonctionner

L'algorithme d'Euclide repose sur une idée simple : remplacer le problème par un problème plus petit qui a la même réponse. On part de la division euclidienne de $a$ par $b$ et on remarque que le PGCD ne change pas si l'on remplace $a$ par le reste.

Démonstration · Preuve de la propriété fondamentale

On écrit $a = bq + r$ . L'idée est de montrer que les couples $(a\,;b)$ et $(b\,;r)$ ont exactement les mêmes diviseurs communs. Si c'est vrai, leur plus grand élément est le même, donc les PGCD sont égaux.

Premier sens. Soit $d$ un diviseur commun de $a$ et de $b$ . Alors $d$ divise $bq$ (multiple de $b$ ), donc $d$ divise la différence $a - bq$ , c'est-à-dire $r$ . Ainsi $d$ divise $b$ et $r$ .

Second sens. Soit $d$ un diviseur commun de $b$ et de $r$ . Alors $d$ divise $bq$ et $r$ , donc leur somme $bq + r = a$ . Ainsi $d$ divise $a$ et $b$ .

Les deux ensembles de diviseurs communs coïncident, donc ils ont le même plus grand élément. $\blacksquare$

Pour $\text{PGCD}(a\,;0)$ : tout entier divise $0$ , donc les diviseurs communs de $a$ et $0$ sont les diviseurs de $a$ , et le plus grand est $|a|$ , soit $a$ lorsque $a>0$ .

L'algorithme d'Euclide, étape par étape

On applique la propriété fondamentale autant de fois que nécessaire. À chaque tour, on remplace le couple $(a\,;b)$ par $(b\,;r)$ . L'algorithme continue jusqu'à trouver un reste nul, puis il s'arrête et retourne le dernier reste non nul ³.

DiviserDivise a par b et note le reste r.
DécalerRemplace a par b, puis b par r.
TesterSi r = 0, stop ; sinon recommence.
LireLe PGCD est le dernier reste non nul.

Les gestes de l'algorithme d'Euclide · On répète les premiers gestes jusqu'à obtenir un reste nul.

Algorithme d'Euclide appliqué à 252 et 198
Ligne	Division	Reste
1	252 = 198 × 1 + 54	54
2	198 = 54 × 3 + 36	36
3	54 = 36 × 1 + 18	18
4	36 = 18 × 2 + 0	0

Algorithme d'Euclide appliqué à 252 et 198 · Le PGCD est le reste de la troisième ligne, juste avant le reste nul.

Pourquoi l'algorithme s'arrête et pourquoi il est exact

En mathématiques expertes, on ne se contente pas de « ça marche sur les exemples ». Deux questions se posent pour tout algorithme : est-ce qu'il termine (terminaison) et est-ce que son résultat est correct (exactitude) ?

Démonstration · Preuve de la terminaison

Notons $r_0 = a$ , $r_1 = b$ , puis $r_{k+1}$ le reste de la division de $r_{k-1}$ par $r_k$ tant que $r_k \neq 0$ . Par définition de la division euclidienne,

$0 \le r_{k+1} < r_k.$

La suite $(r_k)$ est donc formée d'entiers naturels strictement décroissants tant que l'algorithme continue. Or il n'existe pas de suite infinie strictement décroissante d'entiers naturels : au bout d'au plus $b$ divisions, on atteint forcément un reste nul. C'est l'argument utilisé pour justifier que le calcul fait appel à un reste $b'$ vérifiant $0 \le b' < |b|$ ³. $\blacksquare$

Démonstration · Preuve de l'exactitude

D'après la propriété fondamentale, chaque étape conserve le PGCD :

$\text{PGCD}(r_0\,;r_1) = \text{PGCD}(r_1\,;r_2) = \dots = \text{PGCD}(r_n\,;r_{n+1}).$

Comme l'algorithme s'arrête, $r_{n+1}=0$ , et $\text{PGCD}(r_n\,;0)=r_n$ ³. On obtient donc $\text{PGCD}(a\,;b)=r_n$ . $\blacksquare$

Ce raisonnement est un invariant : la quantité « PGCD du couple courant » ne change pas d'un tour à l'autre, alors que les nombres, eux, diminuent.

Écrire l'algorithme en Python et mesurer son efficacité

L'algorithme d'Euclide calcule efficacement le PGCD de deux entiers ³. Il s'écrit en quelques lignes avec une boucle « tant que », qui s'arrête dès que le second nombre est nul ; c'est d'ailleurs l'exemple classique choisi pour introduire cette boucle ². L'écriture suit exactement les étapes du cours.

MéthodeVersion avec une boucle

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

À chaque tour, a % b est le reste de la division de a par b. L'affectation simultanée a, b = b, a % b réalise le décalage : l'ancien b devient a, le reste devient b. Quand b vaut 0, on retourne a, c'est-à-dire le dernier reste non nul.

Reprenons la liste des diviseurs : pour trouver les diviseurs d'un grand entier, il faut le factoriser, ce qui devient très long quand le nombre grandit. L'algorithme d'Euclide, lui, ne demande que des divisions. À chaque tour, les nombres diminuent, et il suffit de peu de lignes même pour de grands nombres. Voici un exemple.

Pour $\text{PGCD}(1\,071\,;462)$ :

$1071 = 462 \times 2 + 147$ $462 = 147 \times 3 + 21$ $147 = 21 \times 7 + 0$

Peu de divisions suffisent et le PGCD vaut $21$ .

Chez les Grecs, un entier représentait une longueur, et deux entiers donnaient les côtés d'un rectangle : le PGCD correspond alors au côté du plus grand carré capable de paver ce rectangle sans trou ni reste ³. L'algorithme découpe le rectangle en carrés de plus en plus petits, par des divisions successives, jusqu'à ce qu'un reste soit nul ³.

Prends un rectangle de $21$ sur $15$ . On y place un carré de côté $15$ (quotient $1$ ), il reste une bande de $15$ sur $6$ . Dans cette bande, on place deux carrés de côté $6$ , il reste une bande de $6$ sur $3$ . Enfin deux carrés de côté $3$ remplissent la bande sans reste. Le plus grand carré qui carrelle tout le rectangle a pour côté $3$ : c'est le PGCD de $21$ et $15$ .

L'algorithme d'Euclide étendu et les coefficients de Bézout

La version étendue de l'algorithme d'Euclide va plus loin que le PGCD : pour deux entiers $a$ et $b$ , elle fournit aussi deux entiers $u$ et $v$ , appelés coefficients de Bézout, qui vérifient $au + bv = \text{PGCD}(a\,;b)$ ⁴. Ces coefficients ne sont pas uniques : on en obtient un couple, pas tous.

ExempleBézout pour 120 et 23

On applique l'algorithme d'Euclide à $120$ et $23$ ⁴ :

$120 = 23 \times 5 + 5$ $23 = 5 \times 4 + 3$ $5 = 3 \times 1 + 2$ $3 = 2 \times 1 + 1$ $2 = 1 \times 2 + 0$

Le PGCD vaut $1$ . On remonte :

$1 = 3 - 2 = 3 - (5 - 3) = 2 \times 3 - 5$ $1 = 2(23 - 4 \times 5) - 5 = 2 \times 23 - 9 \times 5$ $1 = 2 \times 23 - 9(120 - 5 \times 23) = 47 \times 23 - 9 \times 120.$

On obtient $120 \times (-9) + 23 \times 47 = 1$ . Vérification : $-1080 + 1081 = 1$ . Donc $u=-9$ et $v=47$ .

Plutôt que de remonter, on peut calculer les coefficients en même temps que les restes. Le calcul définit une suite finie de triplets $(r_i, u_i, v_i)$ , récurrente d'ordre 2, avec $r_i = a u_i + b v_i$ à chaque étape ⁴. Au départ $r_0=a$ , $(u_0,v_0)=(1,0)$ et $r_1=b$ , $(u_1,v_1)=(0,1)$ . Si $q_i$ est le quotient de $r_{i-1}$ par $r_i$ , alors

$r_{i+1}=r_{i-1}-q_i r_i,\quad u_{i+1}=u_{i-1}-q_i u_i,\quad v_{i+1}=v_{i-1}-q_i v_i.$

Le dernier triplet avant le reste nul donne $\text{PGCD}(a\,;b) = a u_n + b v_n$ ⁴.

Algorithme d'Euclide étendu pour 120 et 23
i	r_i	q_i	u_i	v_i
0	120	—	1	0
1	23	5	0	1
2	5	4	1	-5
3	3	1	-4	21
4	2	1	5	-26
5	1	2	-9	47
6	0	—	—	—

Algorithme d'Euclide étendu pour 120 et 23 · Chaque ligne vérifie r = 120u + 23v ; la ligne de reste 1 donne la relation de Bézout.

Démonstration · Pourquoi la relation reste vraie à chaque ligne

Au départ, $r_0 = a\times 1 + b \times 0$ et $r_1 = a \times 0 + b \times 1$ : la relation est vraie pour les deux premières lignes. Supposons-la vraie pour $r_{i-1}$ et $r_i$ . Alors

$r_{i+1} = r_{i-1} - q_i r_i = (a u_{i-1} + b v_{i-1}) - q_i (a u_i + b v_i) = a(u_{i-1} - q_i u_i) + b(v_{i-1} - q_i v_i),$

ce qui est bien $a u_{i+1} + b v_{i+1}$ . La relation se transmet de ligne en ligne : par récurrence, elle est vraie pour toutes. $\blacksquare$

Un peu d'histoire

L'algorithme d'Euclide figure parmi les plus anciens algorithmes connus, et pourtant il reste d'actualité ³. Il est décrit dans le livre VII des Éléments d'Euclide, vers 300 avant J.-C. ³. Il est aussi présenté dans le livre X, mais sous forme géométrique : il s'agit de trouver une unité de mesure commune pour deux longueurs de segments, en retranchant sans cesse le plus court du plus long ³. Cette soustraction répétée est une manière naïve de calculer une division euclidienne ³.

La paternité d'Euclide est discutée : l'algorithme n'a probablement pas été découvert par lui, qui aurait compilé des résultats d'autres mathématiciens, et il était probablement connu d'Eudoxe de Cnide vers 375 avant J.-C. ³.

Plus tard, l'algorithme a été inventé de manière indépendante en Inde et en Chine, pour résoudre des équations diophantiennes issues de l'astronomie et faire des calendriers plus précis ³. Au Ve siècle, le mathématicien indien Aryabhata le décrit comme le « pulvérisateur », à cause de son efficacité pour résoudre ces équations ³.

La version étendue est associée à Bachet (1612) puis à Bézout (1766) ¹, et Euler en a fait des applications aux fractions continues en 1737 ¹.

Exercices corrigés

Exercice 1 Calculer un PGCD par l'algorithme d'Euclide

★☆☆Environ 8 min

Calcule $\text{PGCD}(1\,071\,;462)$ en détaillant toutes les divisions euclidiennes.

Indice 1

Commence par diviser le plus grand nombre par le plus petit.

Indice 2

Le PGCD est le dernier reste non nul.

Voir la correction pas à pas

On divise $1\,071$ par $462$ : $1071 = 462 \times 2 + 147$ .
On recommence avec $462$ et $147$ : $462 = 147 \times 3 + 21$ .
On recommence avec $147$ et $21$ : $147 = 21 \times 7 + 0$ . Le reste est nul, on s'arrête.
Le dernier reste non nul est $21$ , donc $\text{PGCD}(1071\,;462)=21$ .

Peu de divisions suffisent. Vérification : $1071 = 21 \times 51$ et $462 = 21 \times 22$ , et $51$ et $22$ sont premiers entre eux.

Exercice 2 Carreler un rectangle avec des carreaux carrés

★★☆Environ 12 min

Une salle rectangulaire mesure $1\,260$ cm sur $756$ cm. On veut la carreler entièrement avec des carreaux carrés tous identiques, sans découpe, les plus grands possible.

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

Donne comme réponse numérique le nombre de carreaux.

Indice 1

Le côté du carreau doit diviser les deux dimensions ; on cherche le plus grand.

Indice 2

Le nombre de carreaux est le produit du nombre de carreaux sur la longueur par le nombre sur la largeur.

Voir la correction pas à pas

Le côté $c$ doit diviser $1260$ et $756$ , et être le plus grand possible : $c = \text{PGCD}(1260\,;756)$ .
$1260 = 756 \times 1 + 504$ .
$756 = 504 \times 1 + 252$ .
$504 = 252 \times 2 + 0$ . Donc $c = 252$ cm.
Sur la longueur : $1260 \div 252 = 5$ carreaux. Sur la largeur : $756 \div 252 = 3$ carreaux.
Le nombre total est $5 \times 3 = 15$ carreaux.

Le côté d'un carreau mesure $252$ cm et il faut $15$ carreaux. C'est l'image géométrique du PGCD : le plus grand carré qui carrelle le rectangle.

Exercice 3 Inverse modulaire avec l'algorithme étendu

★★★Environ 15 min

Calcule $\text{PGCD}(35\,;12)$ par l'algorithme d'Euclide.
En remontant les divisions, trouve deux entiers $u$ et $v$ tels que $35u + 12v = 1$ .
En déduire l'inverse de $12$ modulo $35$ , compris entre $0$ et $34$ .

Donne comme réponse numérique cet inverse.

Indice 1

Écris toutes les divisions jusqu'au reste nul, puis isole le reste $1$ .

Indice 2

Si $35u + 12v = 1$ , alors $12v \equiv 1 \pmod{35}$ : l'inverse de $12$ est $v$ modulo $35$ .

Voir la correction pas à pas

$35 = 12 \times 2 + 11$ .
$12 = 11 \times 1 + 1$ .
$11 = 1 \times 11 + 0$ . Le dernier reste non nul est $1$ : $\text{PGCD}(35\,;12)=1$ , les nombres sont premiers entre eux.
On remonte : $1 = 12 - 11 \times 1$ , puis, avec $11 = 35 - 12 \times 2$ : $1 = 12 - (35 - 2 \times 12) = 3 \times 12 - 35$ .
On lit $u = -1$ et $v = 3$ : $35 \times (-1) + 12 \times 3 = 1$ .
Donc $12 \times 3 \equiv 1 \pmod{35}$ et l'inverse de $12$ modulo $35$ est $3$ . Contrôle : $12 \times 3 = 36 = 35 + 1$ .

L'algorithme étendu transforme un calcul de PGCD en calcul d'inverse modulaire. Ici $12 \times 3 = 36 \equiv 1 \pmod{35}$ .

Les questions qu'on se pose

Faut-il toujours diviser le plus grand nombre par le plus petit ?

C'est la façon naturelle de commencer, mais si tu divises dans l'autre sens, le premier tour donne un quotient nul et un reste égal au premier nombre. Le couple est alors simplement remis dans l'ordre, et la suite du calcul est identique. Tu perds seulement une ligne.

À quoi sert l'algorithme d'Euclide, puisque la calculatrice donne le PGCD ?

Il permet de comprendre pourquoi le PGCD existe et comment le calculer sans lister les diviseurs. Surtout, sa version étendue fournit les coefficients de Bézout, qui servent à calculer des inverses modulaires et à résoudre des équations diophantiennes. Historiquement, l'algorithme a servi à ces équations, issues de l'astronomie et des calendriers ³.

Comment vérifier rapidement mon résultat ?

Divise chacun des deux nombres par ton PGCD : les deux divisions doivent tomber juste. Ensuite, contrôle que les deux quotients obtenus sont premiers entre eux, par exemple en refaisant l'algorithme sur eux : leur PGCD doit valoir $1$ . Pour des coefficients de Bézout, remplace $u$ et $v$ dans $au + bv$ et vérifie que tu obtiens le PGCD.

Les coefficients de Bézout sont-ils uniques ?

Non. Si $(u\,;v)$ convient pour $a$ et $b$ , alors $(u + kb\,;\ v - ka)$ convient aussi pour tout entier $k$ relatif, car on ajoute et retire le même multiple de $ab$ . L'algorithme étendu en fournit un couple, pas tous ⁴. Deux réponses différentes peuvent donc être justes ; seule compte la vérification de la relation.

Que se passe-t-il pour des entiers négatifs ?

L'algorithme s'applique sans modification aux entiers relatifs : ce sont alors les valeurs absolues des restes qui diminuent strictement, ce qui garantit encore la terminaison ⁴. Au lycée, on se limite le plus souvent aux entiers naturels.

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 : cours de Terminale (maths expertes)

L'essentiel

Rappels et définition du PGCD

La propriété qui fait tout fonctionner

L'algorithme d'Euclide, étape par étape

Pourquoi l'algorithme s'arrête et pourquoi il est exact

Écrire l'algorithme en Python et mesurer son efficacité

L'algorithme d'Euclide étendu et les coefficients de Bézout

Un peu d'histoire

Exercices corrigés

Exercice 1 Calculer un PGCD par l'algorithme d'Euclide

Exercice 2 Carreler un rectangle avec des carreaux carrés

Exercice 3 Inverse modulaire avec l'algorithme étendu

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur

Tour	a	b
début	21	15
1	15	6
2	6	3
3	3	0