Terminale maths expertes

PGCD, Bézout et équations diophantiennes — 20 exercices corrigés

Savoir chercher un PGCD, remonter l'algorithme d'Euclide et résoudre des équations à solutions entières.

L'essentiel à retenir

  • gcd⁡(a,b)\gcd(a,b) se calcule en remplaçant (a,b)(a,b) par (b,a mod b)(b,a\bmod b).
  • Bézout : il existe u,v∈Zu,v\in\mathbb Z tels que au+bv=gcd⁡(a,b)au+bv=\gcd(a,b).
  • L'équation ax+by=cax+by=c admet des solutions entières si et seulement si gcd⁡(a,b)∣c\gcd(a,b)\mid c.
  • Si gcd⁡(a,b)=1\gcd(a,b)=1, alors une solution particulière (x0,y0)(x_0,y_0) donne x=x0+btx=x_0+bt, y=y0−aty=y_0-at.

Exercice 1 — Algorithme d'Euclide et PGCD — 1

Déterminer gcd⁡(84,30)\gcd(84,30).
  1. Effectuer les divisions euclidiennes successives.
  2. Expliquer quel est le dernier reste non nul.
  3. Écrire une combinaison linéaire des entiers qui vaut le PGCD.
Corrigé détaillé
1. Les divisions de l'algorithme d'Euclide sont : 84=2\times30+24 ; 30=1\times24+6 ; 24=4\times6+0. 2. Le dernier reste non nul vaut 6\boxed{6}, c'est le PGCD. 3. L'identité de Bézout 84×(−1)+30×(3)=6\boxed{84\times(-1)+30\times(3)=6} vérifie le résultat et montre que le PGCD est une combinaison entière des deux nombres.

Exercice 2 — Algorithme d'Euclide et PGCD — 2

Déterminer gcd⁡(145,55)\gcd(145,55).
  1. Effectuer les divisions euclidiennes successives.
  2. Expliquer quel est le dernier reste non nul.
  3. Écrire une combinaison linéaire des entiers qui vaut le PGCD.
Corrigé détaillé
1. Les divisions de l'algorithme d'Euclide sont : 145=2\times55+35 ; 55=1\times35+20 ; 35=1\times20+15 ; 20=1\times15+5 ; 15=3\times5+0. 2. Le dernier reste non nul vaut 5\boxed{5}, c'est le PGCD. 3. L'identité de Bézout 145×(−3)+55×(8)=5\boxed{145\times(-3)+55\times(8)=5} vérifie le résultat et montre que le PGCD est une combinaison entière des deux nombres.

Exercice 3 — Algorithme d'Euclide et PGCD — 3

Déterminer gcd⁡(221,51)\gcd(221,51).
  1. Effectuer les divisions euclidiennes successives.
  2. Expliquer quel est le dernier reste non nul.
  3. Écrire une combinaison linéaire des entiers qui vaut le PGCD.
Corrigé détaillé
1. Les divisions de l'algorithme d'Euclide sont : 221=4\times51+17 ; 51=3\times17+0. 2. Le dernier reste non nul vaut 17\boxed{17}, c'est le PGCD. 3. L'identité de Bézout 221×(1)+51×(−4)=17\boxed{221\times(1)+51\times(-4)=17} vérifie le résultat et montre que le PGCD est une combinaison entière des deux nombres.

Exercice 4 — Algorithme d'Euclide et PGCD — 4

Déterminer gcd⁡(315,128)\gcd(315,128).
  1. Effectuer les divisions euclidiennes successives.
  2. Expliquer quel est le dernier reste non nul.
  3. Écrire une combinaison linéaire des entiers qui vaut le PGCD.
Corrigé détaillé
1. Les divisions de l'algorithme d'Euclide sont : 315=2\times128+59 ; 128=2\times59+10 ; 59=5\times10+9 ; 10=1\times9+1 ; 9=9\times1+0. 2. Le dernier reste non nul vaut 1\boxed{1}, c'est le PGCD. 3. L'identité de Bézout 315×(−13)+128×(32)=1\boxed{315\times(-13)+128\times(32)=1} vérifie le résultat et montre que le PGCD est une combinaison entière des deux nombres.

Exercice 5 — Identité de Bézout et nombres premiers entre eux — 1

Pour les entiers 26 et 15, 1. Calculer le PGCD.
  1. Déterminer deux entiers u,vu,v tels que 26u+15v=126u+15v=1.
  2. En déduire qu'ils sont premiers entre eux.
Corrigé détaillé
1. Les divisions successives donnent 26=1\times15+11 ; 15=1\times11+4 ; 11=2\times4+3 ; 4=1\times3+1 ; 3=3\times1+0 ; le PGCD vaut 1. 2. En remontant l'algorithme, on obtient 26(−4)+15(7)=1\boxed{26(-4)+15(7)=1}. 3. Une combinaison entière égale à 1 implique que tout diviseur commun divise 1 ; le PGCD est donc 1, ce qui caractérise deux entiers premiers entre eux.

Exercice 6 — Identité de Bézout et nombres premiers entre eux — 2

Pour les entiers 35 et 12, 1. Calculer le PGCD.
  1. Déterminer deux entiers u,vu,v tels que 35u+12v=135u+12v=1.
  2. En déduire qu'ils sont premiers entre eux.
Corrigé détaillé
1. Les divisions successives donnent 35=2\times12+11 ; 12=1\times11+1 ; 11=11\times1+0 ; le PGCD vaut 1. 2. En remontant l'algorithme, on obtient 35(−1)+12(3)=1\boxed{35(-1)+12(3)=1}. 3. Une combinaison entière égale à 1 implique que tout diviseur commun divise 1 ; le PGCD est donc 1, ce qui caractérise deux entiers premiers entre eux.

Exercice 7 — Identité de Bézout et nombres premiers entre eux — 3

Pour les entiers 55 et 21, 1. Calculer le PGCD.
  1. Déterminer deux entiers u,vu,v tels que 55u+21v=155u+21v=1.
  2. En déduire qu'ils sont premiers entre eux.
Corrigé détaillé
1. Les divisions successives donnent 55=2\times21+13 ; 21=1\times13+8 ; 13=1\times8+5 ; 8=1\times5+3 ; 5=1\times3+2 ; 3=1\times2+1 ; 2=2\times1+0 ; le PGCD vaut 1. 2. En remontant l'algorithme, on obtient 55(−8)+21(21)=1\boxed{55(-8)+21(21)=1}. 3. Une combinaison entière égale à 1 implique que tout diviseur commun divise 1 ; le PGCD est donc 1, ce qui caractérise deux entiers premiers entre eux.

Exercice 8 — Identité de Bézout et nombres premiers entre eux — 4

Pour les entiers 79 et 32, 1. Calculer le PGCD.
  1. Déterminer deux entiers u,vu,v tels que 79u+32v=179u+32v=1.
  2. En déduire qu'ils sont premiers entre eux.
Corrigé détaillé
1. Les divisions successives donnent 79=2\times32+15 ; 32=2\times15+2 ; 15=7\times2+1 ; 2=2\times1+0 ; le PGCD vaut 1. 2. En remontant l'algorithme, on obtient 79(15)+32(−37)=1\boxed{79(15)+32(-37)=1}. 3. Une combinaison entière égale à 1 implique que tout diviseur commun divise 1 ; le PGCD est donc 1, ce qui caractérise deux entiers premiers entre eux.

Exercice 9 — Équation diophantienne du premier degré — 1

Résoudre dans Z2\mathbb Z^2 l'équation 7x+4y=1.
  1. Justifier l'existence de solutions.
  2. Trouver une solution particulière.
  3. Décrire toutes les solutions.
Corrigé détaillé
1. Comme gcd⁡(7,4)=1\gcd(7,4)=1 divise 1, l'équation admet des solutions entières. 2. L'algorithme de Bézout donne 7(-1)+4(2)=1 ; en multipliant par 1, une solution est (x0,y0)=(−1,2)(x_0,y_0)=(-1,2). 3. Toutes les solutions sont x=−1+4t, y=2−7t, t∈Z\boxed{x=-1+4t,\ y=2-7t,\ t\in\mathbb Z}, ce que l'on vérifie en substituant.

Exercice 10 — Équation diophantienne du premier degré — 2

Résoudre dans Z2\mathbb Z^2 l'équation 9x+5y=2.
  1. Justifier l'existence de solutions.
  2. Trouver une solution particulière.
  3. Décrire toutes les solutions.
Corrigé détaillé
1. Comme gcd⁡(9,5)=1\gcd(9,5)=1 divise 2, l'équation admet des solutions entières. 2. L'algorithme de Bézout donne 9(-1)+5(2)=1 ; en multipliant par 2, une solution est (x0,y0)=(−2,4)(x_0,y_0)=(-2,4). 3. Toutes les solutions sont x=−2+5t, y=4−9t, t∈Z\boxed{x=-2+5t,\ y=4-9t,\ t\in\mathbb Z}, ce que l'on vérifie en substituant.

Exercice 11 — Équation diophantienne du premier degré — 3

Résoudre dans Z2\mathbb Z^2 l'équation 11x+6y=3.
  1. Justifier l'existence de solutions.
  2. Trouver une solution particulière.
  3. Décrire toutes les solutions.
Corrigé détaillé
1. Comme gcd⁡(11,6)=1\gcd(11,6)=1 divise 3, l'équation admet des solutions entières. 2. L'algorithme de Bézout donne 11(-1)+6(2)=1 ; en multipliant par 3, une solution est (x0,y0)=(−3,6)(x_0,y_0)=(-3,6). 3. Toutes les solutions sont x=−3+6t, y=6−11t, t∈Z\boxed{x=-3+6t,\ y=6-11t,\ t\in\mathbb Z}, ce que l'on vérifie en substituant.

Exercice 12 — Équation diophantienne du premier degré — 4

Résoudre dans Z2\mathbb Z^2 l'équation 8x+3y=5.
  1. Justifier l'existence de solutions.
  2. Trouver une solution particulière.
  3. Décrire toutes les solutions.
Corrigé détaillé
1. Comme gcd⁡(8,3)=1\gcd(8,3)=1 divise 5, l'équation admet des solutions entières. 2. L'algorithme de Bézout donne 8(-1)+3(3)=1 ; en multipliant par 5, une solution est (x0,y0)=(−5,15)(x_0,y_0)=(-5,15). 3. Toutes les solutions sont x=−5+3t, y=15−8t, t∈Z\boxed{x=-5+3t,\ y=15-8t,\ t\in\mathbb Z}, ce que l'on vérifie en substituant.

Exercice 13 — Inverse d'une classe et Bézout — 1

Trouver l'inverse de 3 modulo 11.
  1. Vérifier l'existence d'un inverse.
  2. Écrire une identité de Bézout.
  3. Calculer et vérifier cet inverse.
Corrigé détaillé
1. gcd⁡(3,11)=1\gcd(3,11)=1, donc la classe de 3 est inversible modulo 11. 2. L'identité 3(4)+11(−1)=13(4)+11(-1)=1 donne 3(4)≡1(mod11)3(4)\equiv1\pmod{11}. 3. Le reste de 4 modulo 11 vaut 4\boxed{4} ; en effet 3×4≡1(mod11)3\times4\equiv1\pmod{11}.

Exercice 14 — Inverse d'une classe et Bézout — 2

Trouver l'inverse de 5 modulo 13.
  1. Vérifier l'existence d'un inverse.
  2. Écrire une identité de Bézout.
  3. Calculer et vérifier cet inverse.
Corrigé détaillé
1. gcd⁡(5,13)=1\gcd(5,13)=1, donc la classe de 5 est inversible modulo 13. 2. L'identité 5(−5)+13(2)=15(-5)+13(2)=1 donne 5(−5)≡1(mod13)5(-5)\equiv1\pmod{13}. 3. Le reste de -5 modulo 13 vaut 8\boxed{8} ; en effet 5×8≡1(mod13)5\times8\equiv1\pmod{13}.

Exercice 15 — Inverse d'une classe et Bézout — 3

Trouver l'inverse de 7 modulo 17.
  1. Vérifier l'existence d'un inverse.
  2. Écrire une identité de Bézout.
  3. Calculer et vérifier cet inverse.
Corrigé détaillé
1. gcd⁡(7,17)=1\gcd(7,17)=1, donc la classe de 7 est inversible modulo 17. 2. L'identité 7(5)+17(−2)=17(5)+17(-2)=1 donne 7(5)≡1(mod17)7(5)\equiv1\pmod{17}. 3. Le reste de 5 modulo 17 vaut 5\boxed{5} ; en effet 7×5≡1(mod17)7\times5\equiv1\pmod{17}.

Exercice 16 — Inverse d'une classe et Bézout — 4

Trouver l'inverse de 11 modulo 19.
  1. Vérifier l'existence d'un inverse.
  2. Écrire une identité de Bézout.
  3. Calculer et vérifier cet inverse.
Corrigé détaillé
1. gcd⁡(11,19)=1\gcd(11,19)=1, donc la classe de 11 est inversible modulo 19. 2. L'identité 11(7)+19(−4)=111(7)+19(-4)=1 donne 11(7)≡1(mod19)11(7)\equiv1\pmod{19}. 3. Le reste de 7 modulo 19 vaut 7\boxed{7} ; en effet 11×7≡1(mod19)11\times7\equiv1\pmod{19}.

Exercice 17 — Preuve de coprimalité de n et n+1

Démontrer que gcd⁡(n,n+1)\gcd(n,n+1) pour tout entier n≥1n\ge1.
  1. Poser un diviseur commun.
  2. Former une combinaison entière simple.
  3. Conclure.
Corrigé détaillé
1. Tout diviseur commun dd de nn et n+1n+1 divise leur différence (n+1)−n=1(n+1)-n=1. 2. Ainsi d=1d=1. 3. On conclut que gcd⁡(n,n+1)=1\boxed{\gcd(n,n+1)=1}, quel que soit n≥1n\ge1.

Exercice 18 — Preuve de coprimalité de 2n+1 et n+1

Démontrer que gcd⁡(2n+1,n+1)\gcd(2n+1,n+1) pour tout entier n≥0n\ge0.
  1. Poser un diviseur commun.
  2. Former une combinaison entière simple.
  3. Conclure.
Corrigé détaillé
1. Tout diviseur commun divise (2n+1)−2(n+1)=−1(2n+1)-2(n+1)=-1. 2. Il ne peut donc être différent de 1. 3. Ainsi gcd⁡(2n+1,n+1)=1\boxed{\gcd(2n+1,n+1)=1}. L'idée est de combiner les deux expressions linéaires pour obtenir une constante.

Exercice 19 — Preuve de coprimalité de 3n+2 et n+1

Démontrer que gcd⁡(3n+2,n+1)\gcd(3n+2,n+1) pour tout entier n≥0n\ge0.
  1. Poser un diviseur commun.
  2. Former une combinaison entière simple.
  3. Conclure.
Corrigé détaillé
1. Soustraire trois fois le second terme au premier donne (3n+2)−3(n+1)=−1(3n+2)-3(n+1)=-1. 2. Tout diviseur commun divise 1. 3. Donc gcd⁡(3n+2,n+1)=1\boxed{\gcd(3n+2,n+1)=1}.

Exercice 20 — Preuve de coprimalité de 5n+1 et n

Démontrer que gcd⁡(5n+1,n)\gcd(5n+1,n) pour tout entier n≥1n\ge1.
  1. Poser un diviseur commun.
  2. Former une combinaison entière simple.
  3. Conclure.
Corrigé détaillé
1. La combinaison (5n+1)−5n=1(5n+1)-5n=1. 2. Tout diviseur commun de 5n+15n+1 et nn divise 1. 3. Le PGCD vaut 1\boxed1 ; les deux entiers sont premiers entre eux.

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 minSoutien en Maths expertes