insight.Se connecter

Maths expertes · Terminale

PGCD, théorèmes de Bézout et de Gauss : cours et fiche de révision (Maths expertes, Terminale)

Programme officiel, session 2027. Mis à jour le 7 novembre 2026. 9 min de lecture.

Ce que contient ce chapitre

  • Calculer un PGCD avec l'algorithme d'Euclide
  • Écrire le PGCD sous la forme au + bv
  • Prouver que deux entiers sont premiers entre eux
  • Conclure avec le théorème de Gauss
  • Résoudre une équation diophantienne ax + by = c

Le PGCD et les théorèmes de Bézout et de Gauss sont le cœur de l'arithmétique des entiers : l'algorithme d'Euclide figure déjà dans les Éléments, et sa version étendue est due à Bachet (1612) puis à Bézout (1766). Ces outils servent à résoudre des équations en nombres entiers comme 3x+5y=23x+5y=2, à trouver un inverse modulo nn ou à étudier des problèmes de chiffrement. À la fin du chapitre, tu sauras calculer un PGCD, écrire une relation de Bézout, prouver que deux entiers sont premiers entre eux et résoudre une équation diophantienne.

Diviseurs et PGCD

Diviseurs d'un entier

Rappel : dd divise aa s'il existe un entier kk tel que a=kda=kd. Pour lister les diviseurs positifs d'un entier n>0n>0, teste les entiers de 11 à n\sqrt{n} : chaque diviseur dd trouvé en fournit un second, n/dn/d.

Exemple

Diviseurs positifs de 3636 : on teste de 11 à 66. On a 36=1×36=2×18=3×12=4×9=6×636=1\times36=2\times18=3\times12=4\times9=6\times6, et 55 ne divise pas 3636. Les diviseurs positifs de 3636 sont donc 11, 22, 33, 44, 66, 99, 1212, 1818 et 3636.

Définition du PGCD

Soient aa et bb deux entiers non tous deux nuls. Leur plus grand commun diviseur, noté PGCD(a;b)\mathrm{PGCD}(a;b), est le plus grand entier qui divise à la fois aa et bb. On a PGCD(a;b)=PGCD(∣a∣;∣b∣)\mathrm{PGCD}(a;b)=\mathrm{PGCD}(|a|;|b|), et si b≠0b\neq0 divise aa, alors PGCD(a;b)=∣b∣\mathrm{PGCD}(a;b)=|b|.

Exemple

Les diviseurs positifs de 2424 sont 11, 22, 33, 44, 66, 88, 1212 et 2424. Ceux qui divisent aussi 3636 sont 11, 22, 33, 44, 66 et 1212, donc PGCD(24;36)=12\mathrm{PGCD}(24;36)=12. Pour de grands nombres, cette méthode est trop longue : on utilise l'algorithme d'Euclide.

L'algorithme d'Euclide

Propriété. Si a=bq+ra=bq+r avec b≠0b\neq0 et qq, rr entiers, alors les diviseurs communs à aa et bb sont exactement les diviseurs communs à bb et rr. Donc PGCD(a;b)=PGCD(b;r)\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r).

En effet, un diviseur commun à aa et bb divise r=a−bqr=a-bq, et un diviseur commun à bb et rr divise a=bq+ra=bq+r.

L'algorithme. Pour a≥b>0a\geq b>0, divise aa par bb, puis bb par le reste obtenu, puis ce reste par le nouveau reste, et ainsi de suite. Les restes sont des entiers naturels strictement décroissants, donc l'un d'eux finit par être nul. Le PGCD est le dernier reste non nul.

Exemple

Calcul de PGCD(252;198)\mathrm{PGCD}(252;198) :

252 = 1 × 198 + 54198 = 3 × 54 + 3654 = 1 × 36 + 1836 = 2 × 18 + 0Dernier reste non nul : 18

Le dernier reste non nul est 1818, donc PGCD(252;198)=18\mathrm{PGCD}(252;198)=18.

Conséquence. Chaque division conserve les diviseurs communs : les diviseurs communs à aa et bb sont exactement les diviseurs de leur PGCD. Ici, ce sont ceux de 1818 : 11, 22, 33, 66, 99 et 1818, et leurs opposés.

L'identité de Bézout

Théorème. Soient aa et bb deux entiers non tous deux nuls, et d=PGCD(a;b)d=\mathrm{PGCD}(a;b). Il existe deux entiers uu et vv tels que au+bv=dau+bv=d. Un tel couple (u;v)(u;v) est un couple de Bézout ; il n'est pas unique.

Trouver un couple : l'algorithme d'Euclide étendu

Dans l'algorithme d'Euclide, isole chaque reste, puis remonte depuis l'avant-dernière division en remplaçant les restes un à un.

Exemple

Avec 252252 et 198198 : 54=252−19854=252-198, 36=198−3×5436=198-3\times54 et 18=54−3618=54-36. On remonte :

18=54−(198−3×54)=4×54−19818=54-(198-3\times54)=4\times54-198 18=4×(252−198)−198=4×252−5×19818=4\times(252-198)-198=4\times252-5\times198

Vérification : 4×252−5×198=1008−990=184\times252-5\times198=1008-990=18. Le couple (4;−5)(4;-5) convient.

Démonstration (à connaître)

Soit EE l'ensemble des entiers strictement positifs de la forme ax+byax+by, avec xx et yy entiers. EE contient a2+b2a^2+b^2, donc il est non vide et admet un plus petit élément m=au0+bv0m=au_0+bv_0.

  • mm divise aa : la division euclidienne donne a=mq+ra=mq+r avec 0≤r<m0 \leq r < m, donc r=a−mq=a(1−qu0)+b(−qv0)r=a-mq=a(1-qu_0)+b(-qv_0) est de la forme ax+byax+by. Si r>0r>0, rr serait un élément de EE plus petit que mm : impossible. Donc r=0r=0. De même, mm divise bb. Ainsi mm est un diviseur commun positif, et m≤dm\leq d.
  • dd divise aa et bb, donc dd divise au0+bv0=mau_0+bv_0=m, d'où d≤md\leq m.

Donc m=dm=d, c'est-à-dire d=au0+bv0d=au_0+bv_0.

Entiers premiers entre eux et théorème de Bézout

Deux entiers aa et bb sont premiers entre eux lorsque PGCD(a;b)=1\mathrm{PGCD}(a;b)=1 : leurs seuls diviseurs communs sont 11 et −1-1. Ainsi 88 et 1515 sont premiers entre eux, sans qu'aucun des deux soit premier : les diviseurs positifs de 88 sont 11, 22, 44, 88, et seul 11 divise 1515.

Théorème de Bézout. aa et bb sont premiers entre eux si et seulement s'il existe deux entiers uu et vv tels que au+bv=1au+bv=1.

Exemples. Pour tout entier nn :

  • (n+1)×1+n×(−1)=1(n+1)\times1+n\times(-1)=1, donc nn et n+1n+1 sont premiers entre eux ;
  • (2n+1)×1+n×(−2)=1(2n+1)\times1+n\times(-2)=1, donc 2n+12n+1 et nn sont premiers entre eux.

Démonstration : si PGCD(a;b)=1\mathrm{PGCD}(a;b)=1, l'identité de Bézout fournit uu et vv. Réciproquement, si au+bv=1au+bv=1, tout diviseur commun à aa et bb divise au+bv=1au+bv=1, donc vaut 11 ou −1-1.

Attention

une égalité au+bv=kau+bv=k ne prouve pas que PGCD(a;b)=k\mathrm{PGCD}(a;b)=k, seulement que le PGCD divise kk. Par exemple, 3×4+5×(−2)=23\times4+5\times(-2)=2, alors que PGCD(3;5)=1\mathrm{PGCD}(3;5)=1.

Diviser par le PGCD

Propriété. Si d=PGCD(a;b)d=\mathrm{PGCD}(a;b), avec a=da′a=da' et b=db′b=db', alors a′a' et b′b' sont premiers entre eux. En effet, au+bv=dau+bv=d s'écrit da′u+db′v=dda'u+db'v=d, et en divisant par dd : a′u+b′v=1a'u+b'v=1. Exemple : 252=18×14252=18\times14 et 198=18×11198=18\times11, donc 1414 et 1111 sont premiers entre eux.

Application : inverse modulo nn

Si aa et nn sont premiers entre eux, une relation au+nv=1au+nv=1 donne au≡1 [n]au\equiv1\ [n] : uu est un inverse de aa modulo nn. Il permet de résoudre ax≡b [n]ax\equiv b\ [n].

Exemple

Inverse de 77 modulo 2626. Euclide : 26=3×7+526=3\times7+5, 7=1×5+27=1\times5+2 et 5=2×2+15=2\times2+1. On remonte :

1=5−2×2=5−2×(7−5)=3×5−2×71=5-2\times2=5-2\times(7-5)=3\times5-2\times7 1=3×(26−3×7)−2×7=3×26−11×71=3\times(26-3\times7)-2\times7=3\times26-11\times7

Donc 7×(−11)≡1 [26]7\times(-11)\equiv1\ [26]. Comme −11≡15 [26]-11\equiv15\ [26], 1515 est un inverse de 77 modulo 2626 : 7×15=105=4×26+17\times15=105=4\times26+1. Pour résoudre 7x≡3 [26]7x\equiv3\ [26], multiplie par 1515 : 105x≡45 [26]105x\equiv45\ [26], soit x≡19 [26]x\equiv19\ [26] car 105≡1105\equiv1 et 45≡1945\equiv19 modulo 2626. Réciproquement, si x≡19 [26]x\equiv19\ [26], alors 7x≡133≡3 [26]7x\equiv133\equiv3\ [26].

Le théorème de Gauss

Théorème. Soient aa, bb et cc des entiers. Si aa divise bcbc et si aa et bb sont premiers entre eux, alors aa divise cc.

Exemple

Cherchons les couples d'entiers (x;y)(x;y) tels que 4x=9y4x=9y. 99 divise 4x4x, et PGCD(9;4)=1\mathrm{PGCD}(9;4)=1 car 9×1+4×(−2)=19\times1+4\times(-2)=1. D'après le théorème de Gauss, 99 divise xx : x=9kx=9k avec k∈Zk\in\mathbb{Z}. Alors 36k=9y36k=9y, soit y=4ky=4k. Réciproquement, 4×9k=9×4k4\times9k=9\times4k. Les solutions sont les couples (9k;4k)(9k;4k), k∈Zk\in\mathbb{Z}.

L'hypothèse est indispensable : 66 divise 4×3=124\times3=12, mais 66 ne divise ni 44 ni 33 ; ici PGCD(6;4)=2\mathrm{PGCD}(6;4)=2.

Démonstration (à connaître). Comme PGCD(a;b)=1\mathrm{PGCD}(a;b)=1, le théorème de Bézout donne deux entiers uu et vv tels que au+bv=1au+bv=1. En multipliant par cc : acu+bcv=cacu+bcv=c. Or aa divise acuacu, et aa divise bcbc donc bcvbcv : aa divise leur somme, c'est-à-dire cc.

Conséquence. Si aa et bb divisent nn et sont premiers entre eux, alors abab divise nn. En effet, n=akn=ak et bb divise akak en étant premier avec aa, donc bb divise kk (Gauss) : k=bk′k=bk' et n=abk′n=abk'. Sans l'hypothèse, c'est faux : 44 et 66 divisent 1212, mais 2424 ne divise pas 1212.

Équations diophantiennes ax+by=cax+by=c

On cherche les couples d'entiers (x;y)(x;y) tels que ax+by=cax+by=c, avec aa, bb, cc entiers et aa, bb non nuls.

Existence de solutions

Propriété. L'équation ax+by=cax+by=c admet des solutions entières si et seulement si d=PGCD(a;b)d=\mathrm{PGCD}(a;b) divise cc.

  • Si (x;y)(x;y) est solution, dd divise aa et bb, donc ax+by=cax+by=c.
  • Si c=dkc=dk, un couple de Bézout au+bv=dau+bv=d donne a(uk)+b(vk)=ca(uk)+b(vk)=c.

Ainsi, 6x+9y=46x+9y=4 n'a aucune solution entière : PGCD(6;9)=3\mathrm{PGCD}(6;9)=3 ne divise pas 44.

La méthode, pas à pas

Exemple

Résoudre dans Z2\mathbb{Z}^2 l'équation (E)(E) : 9x+15y=69x+15y=6.

  1. Simplifier. PGCD(9;15)=3\mathrm{PGCD}(9;15)=3 divise 66. En divisant par 33, (E)(E) équivaut à 3x+5y=23x+5y=2, avec 33 et 55 premiers entre eux.
  2. Solution particulière. 3×(−1)+5×1=23\times(-1)+5\times1=2 : le couple (−1;1)(-1;1) convient. Si aucune ne saute aux yeux, multiplie un couple de Bézout par 22 : 3×2+5×(−1)=13\times2+5\times(-1)=1 donne (4;−2)(4;-2).
  3. Soustraire. Si 3x+5y=23x+5y=2, en retranchant 3×(−1)+5×1=23\times(-1)+5\times1=2, on obtient 3(x+1)+5(y−1)=03(x+1)+5(y-1)=0, soit 3(x+1)=5(1−y)3(x+1)=5(1-y).
  4. Appliquer Gauss. 55 divise 3(x+1)3(x+1) et PGCD(5;3)=1\mathrm{PGCD}(5;3)=1, donc 55 divise x+1x+1 : x=−1+5kx=-1+5k, k∈Zk\in\mathbb{Z}. En reportant, 3×5k=5(1−y)3\times5k=5(1-y), d'où 1−y=3k1-y=3k et y=1−3ky=1-3k.
  5. Vérifier la réciproque. 3(−1+5k)+5(1−3k)=−3+15k+5−15k=23(-1+5k)+5(1-3k)=-3+15k+5-15k=2 pour tout kk.

Les solutions de (E)(E) sont les couples (−1+5k;1−3k)(-1+5k;1-3k), k∈Zk\in\mathbb{Z}. Pour k=1k=1, on retrouve (4;−2)(4;-2).

Les pièges

  • Gauss sans son hypothèse. Avant d'écrire « aa divise cc », justifie que aa et bb sont premiers entre eux.
  • Un PGCD lu dans n'importe quelle relation. au+bv=kau+bv=k ne donne pas PGCD(a;b)=k\mathrm{PGCD}(a;b)=k : seule l'égalité au+bv=1au+bv=1 permet de conclure.
  • L'équation non simplifiée. Dans 9x+15y=69x+15y=6, Gauss ne s'applique pas à 99 et 1515 : divise d'abord par leur PGCD.
  • La réciproque oubliée. La méthode donne des conditions nécessaires : vérifie que les couples trouvés sont solutions.
  • Deux paramètres différents. Dans (−1+5k;1−3k)(-1+5k;1-3k), c'est le même kk dans les deux coordonnées.
  • Une erreur de signe en remontant Euclide. Recalcule toujours au+bvau+bv à la fin.
  • Une congruence divisée. De 4x≡8 [12]4x\equiv8\ [12], on ne déduit pas x≡2 [12]x\equiv2\ [12] : x=5x=5 convient aussi. On ne simplifie que par un nombre inversible modulo nn, en multipliant par son inverse.
  • « Premiers entre eux » confondu avec « premiers ». 88 et 1515 sont premiers entre eux sans être premiers.

Ce qu'il faut retenir

  • PGCD(a;b)\mathrm{PGCD}(a;b) est le plus grand diviseur commun à aa et bb ; leurs diviseurs communs sont les diviseurs de leur PGCD.
  • Si a=bq+ra=bq+r, alors PGCD(a;b)=PGCD(b;r)\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r) ; par l'algorithme d'Euclide, le PGCD est le dernier reste non nul.
  • Il existe des entiers uu et vv tels que au+bv=PGCD(a;b)au+bv=\mathrm{PGCD}(a;b) (identité de Bézout).
  • Théorème de Bézout : aa et bb sont premiers entre eux si et seulement s'il existe uu, vv entiers tels que au+bv=1au+bv=1.
  • Si d=PGCD(a;b)d=\mathrm{PGCD}(a;b), a=da′a=da' et b=db′b=db', alors a′a' et b′b' sont premiers entre eux.
  • Si au+nv=1au+nv=1, alors uu est un inverse de aa modulo nn.
  • Théorème de Gauss : si aa divise bcbc et PGCD(a;b)=1\mathrm{PGCD}(a;b)=1, alors aa divise cc.
  • ax+by=cax+by=c a des solutions entières si et seulement si PGCD(a;b)\mathrm{PGCD}(a;b) divise cc ; on les trouve par solution particulière, Gauss, puis réciproque.

À l'épreuve

En devoir surveillé, les calculs se posent à la main et les questions sont très codifiées :

  • « Calculer PGCD(a;b)\mathrm{PGCD}(a;b) par l'algorithme d'Euclide » : écris toutes les divisions et conclus par « le dernier reste non nul est… ».
  • « Déterminer un couple (u;v)(u;v) tel que au+bv=1au+bv=1 » : remonte ligne par ligne et termine par la vérification.
  • « Montrer que aa et bb sont premiers entre eux » : exhibe une relation au+bv=1au+bv=1 et cite le théorème de Bézout.
  • « Résoudre dans Z2\mathbb{Z}^2 l'équation ax+by=cax+by=c » : souvent découpé en sous-questions (solution particulière, puis solutions générales). Le professeur attend le théorème de Gauss cité avec son hypothèse, la réciproque et l'ensemble des couples avec « k∈Zk\in\mathbb{Z} ».
  • Les démonstrations du cours, l'écriture du PGCD sous la forme ax+byax+by et le théorème de Gauss, peuvent être demandées telles quelles.

Ce qui coûte des points : un théorème appliqué sans vérifier ses hypothèses, une réciproque oubliée, un couple de Bézout non vérifié, une réponse sans phrase de conclusion.

À retenir

  • Calculer un PGCD avec l'algorithme d'Euclide

    Le PGCD de aa et bb, non tous deux nuls, est le plus grand entier qui divise à la fois aa et bb.Si a=bq+ra=bq+r, alors PGCD(a;b)=PGCD(b;r)\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r).Algorithme d'Euclide : enchaîne les divisions euclidiennes ; le PGCD est le dernier reste non nul.Les diviseurs communs à aa et bb sont exactement les diviseurs de leur PGCD.
  • Écrire le PGCD sous la forme au + bv

    Identité de Bézout : si d=PGCD(a;b)d=\mathrm{PGCD}(a;b), il existe des entiers uu et vv tels que au+bv=dau+bv=d.Pour trouver (u;v)(u;v), isole chaque reste de l'algorithme d'Euclide, puis remonte depuis l'avant-dernière division.Vérifie toujours le couple obtenu en recalculant au+bvau+bv.Un couple de Bézout n'est pas unique.
  • Prouver que deux entiers sont premiers entre eux

    aa et bb sont premiers entre eux lorsque PGCD(a;b)=1\mathrm{PGCD}(a;b)=1.Théorème de Bézout : c'est le cas si et seulement s'il existe des entiers uu et vv tels que au+bv=1au+bv=1.Si d=PGCD(a;b)d=\mathrm{PGCD}(a;b), a=da′a=da' et b=db′b=db', alors a′a' et b′b' sont premiers entre eux.Si au+nv=1au+nv=1, alors au≡1 [n]au\equiv1\ [n] : uu est un inverse de aa modulo nn.
  • Conclure avec le théorème de Gauss

    Théorème de Gauss : si aa divise bcbc et si aa et bb sont premiers entre eux, alors aa divise cc.Preuve : au+bv=1au+bv=1 donne acu+bcv=cacu+bcv=c, et aa divise acuacu et bcvbcv.Sans l'hypothèse, c'est faux : 66 divise 4×34\times3 sans diviser 44 ni 33.Si aa et bb, premiers entre eux, divisent nn, alors abab divise nn.
  • Résoudre une équation diophantienne ax + by = c

    ax+by=cax+by=c a des solutions entières si et seulement si PGCD(a;b)\mathrm{PGCD}(a;b) divise cc.Divise d'abord par le PGCD pour obtenir des coefficients premiers entre eux.Trouve une solution particulière, soustrais les deux égalités, puis applique le théorème de Gauss.Vérifie la réciproque et écris les solutions avec un seul paramètre k∈Zk\in\mathbb{Z}.

Teste-toi

Trois questions. Réponds, la correction s’affiche.

Question 1 sur 3
Quel est le PGCD de 4848 et 1818 ?

Correction

48=2×18+1248=2\times18+12 ; 18=1×12+618=1\times12+6 ; 12=2×6+012=2\times6+0.Le dernier reste non nul est 66, donc PGCD(48;18)=6\mathrm{PGCD}(48;18)=6.Erreur classique : répondre 1212, le premier reste — le PGCD est le dernier reste non nul, celui qui précède le reste 00.
Question 2 sur 3
Parmi ces couples, lequel est formé de deux entiers premiers entre eux ?

Correction

35=2×12+1135=2\times12+11 puis 12=1×11+112=1\times11+1 : le dernier reste non nul est 11.Donc PGCD(12;35)=1\mathrm{PGCD}(12;35)=1 : 1212 et 3535 sont premiers entre eux, sans être premiers.Erreur classique : écarter 1212 et 3535 parce qu'ils ne sont pas premiers — être premiers entre eux ne demande pas que chaque nombre soit premier.
Question 3 sur 3
Laquelle de ces équations admet des solutions dans Z2\mathbb{Z}^2 ?

Correction

PGCD(6;9)=3\mathrm{PGCD}(6;9)=3 et 33 divise 15=3×515=3\times5 : l'équation a des solutions.Par exemple (1;1)(1;1) convient : 6+9=156+9=15.Erreur classique : croire qu'une équation ax+by=cax+by=c a toujours une solution entière — il faut que PGCD(a;b)\mathrm{PGCD}(a;b) divise cc.

Dans Insight, ce chapitre a 85 questions, et l’app te les repose au bon moment pour que tu ne les oublies pas avant le bac.

Contenu préparé avec l’aide d’outils d’IA, vérifié.

Réviser ce chapitre gratuitement