PGCD, Bézout et Gauss Terminale : 10 exercices corrigés

Le cours de PGCD, Bézout et Gauss conduit de l'algorithme d'Euclide à une identité de Bézout utilisable pour calculer un inverse modulo.

Les exercices vérifient chaque hypothèse du théorème de Gauss, puis distinguent l'existence d'une solution de la famille complète d'une équation diophantienne en solutions entières.

Euclide et Bézout

Conserver les divisions pour pouvoir les remonter.

Exercice 1 : Algorithme d’Euclide

Facile

Calculer le PGCD de 252 et 198.

  1. Effectuer les divisions successives.
  2. Conclure.
Voir le corrigé
  1. 252=198+54, 198=3×54+36, 54=36+18252=198+54,\ 198=3\times54+36,\ 54=36+18.
  2. Le dernier reste non nul est 18, donc gcd⁡(252,198)=18\gcd(252,198)=18.

Exercice 2 : Coefficients de Bézout

Moyen

Travailler avec 35 et 22.

  1. Calculer leur PGCD.
  2. Trouver une identité de Bézout.
Voir le corrigé
  1. L'algorithme d'Euclide donne 1.
  2. En remontant, 1=8×22−5×351=8\times22-5\times35.

Exercice 3 : Inverse modulaire par Bézout

Moyen

Déterminer l'inverse de 17 modulo 43.

  1. Écrire une identité de Bézout.
  2. En déduire l'inverse.
Voir le corrigé
  1. Euclide donne 1=2×43−5×171=2\times43-5\times17.
  2. −5≡38(mod43)-5\equiv38\pmod{43}, donc l'inverse de 17 est 38.

Exercice 4 : Application de Gauss

Moyen

On sait que 14 divise 9n9n.

  1. Vérifier l'hypothèse de Gauss.
  2. Conclure.
Voir le corrigé
  1. gcd⁡(14,9)=1\gcd(14,9)=1.
  2. Par le théorème de Gauss, 14 divise n.

Équations diophantiennes

Trouver une solution puis toute la famille.

Exercice 5 : Existence de solutions

Facile

Étudier 18x+30y=718x+30y=7.

  1. Calculer le PGCD des coefficients.
  2. Conclure sur les solutions entières.
Voir le corrigé
  1. gcd⁡(18,30)=6\gcd(18,30)=6.
  2. 6 ne divise pas 7, donc l'équation n'a aucune solution entière.

Exercice 6 : Famille complète

Moyen

Résoudre 35x+22y=135x+22y=1.

  1. Donner une solution particulière.
  2. Donner toutes les solutions.
Voir le corrigé
  1. L'identité 1=−5×35+8×221=-5\times35+8\times22 donne (x0,y0)=(−5,8)(x_0,y_0)=(-5,8).
  2. x=−5+22k, y=8−35kx=-5+22k,\ y=8-35k, avec k∈Zk\in\mathbb Z.

Exercice 7 : Contrainte positive

Difficile

Une association achète des lots à 7 euros et à 11 euros pour exactement 100 euros.

  1. Résoudre 7x+11y=1007x+11y=100 dans les entiers.
  2. Imposer x,y≥0x,y\geq0.
  3. Contrôler le total.
  4. Combien de lots l'association achète-t-elle ?
Indication
Commencer par une solution particulière, puis borner le paramètre.
Voir le corrigé
  1. Une solution est (8,4)(8,4), et toutes les solutions sont x=8+11k, y=4−7kx=8+11k,\ y=4-7k.
  2. Les inégalités imposent k=0k=0, donc 8 lots à 7 euros et 4 lots à 11 euros.
  3. 7×8+11×4=56+44=1007\times8+11\times4=56+44=100.
  4. Elle achète 8+4=128+4=12 lots au total.

Exercice 8 : Rationalité d’une fraction

Difficile

Supposons que p et q sont premiers entre eux et que q∣p2q\mid p^2.

  1. Montrer que tout facteur premier de q divise p.
  2. Conclure.
Indication
Appliquer Gauss à un facteur premier de q.
Voir le corrigé
  1. Si un premier r divise q, alors r divise p2p^2, donc r divise p par Gauss.
  2. Aucun premier ne peut diviser à la fois p et q ; ainsi q n'a pas de facteur premier et q=1q=1.

Coprimalité paramétrée

Ramener un PGCD à celui de deux entiers simples.

Exercice 9 : Deux entiers consécutifs

Facile

Montrer que n et n+1n+1 sont premiers entre eux pour tout entier n.

  1. Soit d un diviseur commun. Montrer qu'il divise une différence.
  2. Conclure sur le PGCD.
Voir le corrigé
  1. Si d divise n et n+1n+1, alors d divise (n+1)−n=1(n+1)-n=1.
  2. Le seul diviseur positif de 1 est 1, donc gcd⁡(n,n+1)=1\gcd(n,n+1)=1.

Exercice 10 : Fraction toujours irréductible

Moyen

Pour n∈Nn\in\mathbb N, étudier la fraction 2n+1n+1\frac{2n+1}{n+1}.

  1. Transformer le PGCD par combinaison linéaire.
  2. Conclure sur la fraction.
Voir le corrigé
  1. Tout diviseur commun de 2n+12n+1 et n+1n+1 divise 2(n+1)−(2n+1)=12(n+1)-(2n+1)=1.
  2. Le PGCD vaut 1, donc la fraction est irréductible pour tout n.
Partager