Accueil › Exercices › maths expertes › Le pgcd et les théorèmes de bézout et de gauss
Exercices sur le PGCD, Bézout et Gauss en maths expertes
⚡ Quiz pour démarrer · 3 questionsPGCD ( 12 ; 18 ) vaut :
3 2 36 6
Plus grand diviseur commun : 6 .
36 est le PPCM.
6 divise aussi les deux.
6 est plus grand que 2 .
a et b sont premiers entre eux si et seulement s'il existe u , v entiers tels que :
a u + b v = 1 a + b = 1 a u + b v = 0 ab = 1
C'est le théorème de Bézout.
a u + b v = 0 a toujours des solutions.
Ce n'est pas la condition.
Ce n'est pas la condition.
5 divise 3 n . On peut en déduire que :
3 divise n rien 5 divise n 15 divise n
Gauss : 5 et 3 sont premiers entre eux.
C'est 5 qui divise 3 n .
On ne sait rien sur la divisibilité par 3 .
Le théorème de Gauss permet de conclure.
↻ Recommencer le quiz
facile moyen difficile
🖨 Imprimer Exercice 1 L'algorithme d'Euclide À l'aide de l'algorithme d'Euclide, calcule PGCD ( 1 071 ; 462 ) .
Voir le corrigé 1 071 = 2 × 462 + 147 ; 462 = 3 × 147 + 21 ; 147 = 7 × 21 + 0 .
Le PGCD est le dernier reste non nul : PGCD ( 1 071 ; 462 ) = 21 .
🖨 Imprimer Exercice 2 Premiers entre eux ? Calcule PGCD ( 35 ; 18 ) et PGCD ( 84 ; 126 ) . Quels nombres sont premiers entre eux ?
Voir le corrigé 35 = 18 + 17 , 18 = 17 + 1 , 17 = 17 × 1 : PGCD ( 35 ; 18 ) = 1 , 35 et 18 sont premiers entre eux.
126 = 84 + 42 , 84 = 2 × 42 : PGCD ( 84 ; 126 ) = 42 .🖨 Imprimer Exercice 3 Des coefficients de Bézout En remontant l'algorithme d'Euclide de l'exercice 2, trouve deux entiers u et v tels que 35 u + 18 v = 1 .
Voir le corrigé 1 = 18 − 17 et 17 = 35 − 18 , donc 1 = 18 − ( 35 − 18 ) = 2 × 18 − 35 . u = − 1 et v = 2 .
🖨 Imprimer Exercice 4 Le théorème de Gauss a. On sait que 7 divise 4 n . Montre que 7 divise n .
b. Si 6 divise 4 n , 6 divise-t-il forcément n ?Voir le corrigé a. 7 divise 4 n et PGCD ( 7 ; 4 ) = 1 : d'après le théorème de Gauss, 7 divise n .
b. Non : 6 divise 4 × 3 = 12 mais pas 3 . Ici PGCD ( 6 ; 4 ) = 2 = 1 : Gauss ne s'applique pas.🖨 Imprimer Exercice 5 L'équation 5x + 3y = 1 Résous dans Z 2 l'équation 5 x + 3 y = 1 .
Voir le corrigé Solution particulière : ( 2 ; − 3 ) car 10 − 9 = 1 . Si ( x ; y ) est solution, 5 ( x − 2 ) = 3 ( − 3 − y ) .
5 divise 3 ( − 3 − y ) et PGCD ( 5 ; 3 ) = 1 : 5 ∣ − 3 − y , soit y = − 3 − 5 k , puis x = 2 + 3 k .
Réciproquement, ces couples conviennent. S = {( 2 + 3 k ; − 3 − 5 k ) , k ∈ Z } .
Pour résoudre a x + b y = c : on vérifie que PGCD ( a , b ) divise c , on trouve une solution particulière, on soustrait, puis on applique le théorème de Gauss.
🖨 Imprimer Exercice 6 Des solutions ou pas ? a. L'équation 12 x + 18 y = 7 a-t-elle des solutions entières ?
b. Résous 12 x + 18 y = 30 dans Z 2 .Voir le corrigé a. 12 x + 18 y est toujours multiple de 6 , pas 7 : aucune solution .
b. On divise par 6 : 2 x + 3 y = 5 , solution particulière ( 1 ; 1 ) . 2 ( x − 1 ) = 3 ( 1 − y ) donne x = 1 + 3 k , y = 1 − 2 k , k ∈ Z .🖨 Imprimer Exercice 7 Un inverse modulo 26 Trouve un entier u tel que 7 u ≡ 1 [ 26 ] , à l'aide de l'algorithme d'Euclide.
Voir le corrigé 26 = 3 × 7 + 5 , 7 = 5 + 2 , 5 = 2 × 2 + 1 . En remontant : 1 = 5 − 2 × 2 = 5 − 2 ( 7 − 5 ) = 3 × 5 − 2 × 7 = 3 ( 26 − 3 × 7 ) − 2 × 7 = 3 × 26 − 11 × 7 .
Donc 7 × ( − 11 ) ≡ 1 [ 26 ] et u ≡ − 11 ≡ 15 [ 26 ] (vérification : 7 × 15 = 105 = 4 × 26 + 1 ).
🖨 Imprimer Exercice 8 Un PGCD qui dépend de n a. Montre que PGCD ( n ; n + 1 ) = 1 pour tout entier n .
b. Montre que PGCD ( 2 n + 1 ; n + 3 ) divise 5 , puis donne les valeurs de n pour lesquelles il vaut 5 .Voir le corrigé a. Un diviseur commun divise ( n + 1 ) − n = 1 .
b. 2 n + 1 = 2 ( n + 3 ) − 5 : un diviseur commun divise 5 , donc le PGCD vaut 1 ou 5 . Il vaut 5 si 5 ∣ n + 3 (alors 5 ∣ 2 n + 1 aussi), soit n ≡ 2 [ 5 ] .🖨 Imprimer Exercice 9 Payer avec des billets de 7 et 11 Dans un jeu, on dispose de billets de 7 et de 11 crédits. On veut payer exactement 100 crédits, sans rendu de monnaie.
a. Résous 7 x + 11 y = 100 dans Z 2 (vérifie que ( 8 ; 4 ) est solution).
b. Combien de billets de chaque sorte faut-il ?Voir le corrigé a. 56 + 44 = 100 . 7 ( x − 8 ) = 11 ( 4 − y ) et Gauss : x = 8 + 11 k , y = 4 − 7 k , k ∈ Z .
b. On veut x ⩾ 0 et y ⩾ 0 : k ⩾ − 11 8 et k ⩽ 7 4 , donc k = 0 . 8 billets de 7 et 4 billets de 11 .🖨 Imprimer Exercice 10 Gauss avec un produit Soit n un entier tel que 15 divise 4 n . Montre que n est un multiple de 15 . Déduis-en les solutions de 4 n ≡ 0 [ 15 ] .
Voir le corrigé PGCD ( 15 ; 4 ) = 1 et 15 ∣ 4 n : par le théorème de Gauss, 15 ∣ n . Les solutions sont n ≡ 0 [ 15 ] .
🖨 Imprimer Exercice 11 Deux conditions de reste Détermine les entiers x tels que x ≡ 2 [ 3 ] et x ≡ 3 [ 5 ] .
Voir le corrigé x = 3 + 5 k et 3 + 5 k ≡ 2 [ 3 ] ⟺ 2 k ≡ − 1 ≡ 2 [ 3 ] ⟺ k ≡ 1 [ 3 ] (2 est inversible modulo 3 ).
Donc k = 1 + 3 m et x = 8 + 15 m . x ≡ 8 [ 15 ] .
🖨 Imprimer Exercice 12 Retrouver deux nombres Détermine les couples d'entiers naturels ( a ; b ) avec a ⩽ b , de PGCD 6 et de PPCM 72 . (On rappelle que ab = PGCD × PPCM .)
Voir le corrigé a = 6 a ′ , b = 6 b ′ avec a ′ et b ′ premiers entre eux, et ab = 432 donne a ′ b ′ = 12 .
Couples premiers entre eux de produit 12 : ( 1 ; 12 ) et ( 3 ; 4 ) (pas ( 2 ; 6 ) ). ( 6 ; 72 ) et ( 18 ; 24 ) .
🖨 Imprimer Exercice 13 type contrôle Carrelage et engrenages Partie A : le carrelage
On veut recouvrir un sol rectangulaire de 252 cm sur 198 cm avec des carreaux carrés identiques, sans découpe, les plus grands possible.
1. Quelle est la taille des carreaux ? Combien en faut-il ?
Partie B : les engrenages
Deux roues dentées de 24 et 36 dents sont engrenées. On marque une dent de chaque roue au point de contact.
2. Au bout de combien de dents passées les deux marques se retrouvent-elles en contact pour la première fois ?
3. Combien de tours chaque roue a-t-elle alors effectués ?
4. Vérifie que PGCD ( 24 ; 36 ) × PPCM ( 24 ; 36 ) = 24 × 36 .Voir le corrigé 1. Le côté divise 252 et 198 , et doit être le plus grand : PGCD ( 252 ; 198 ) = 18 . Carreaux de 18 cm , soit 14 × 11 = 154 carreaux .
2. Le nombre de dents passées doit être un multiple de 24 et de 36 : PPCM ( 24 ; 36 ) = 72 .
3. 3 tours pour la petite roue, 2 pour la grande .
4. PGCD = 12 et 12 × 72 = 864 = 24 × 36 .🖨 Imprimer Exercice 14 type contrôle Des points à coordonnées entières On considère la droite D d'équation 3 x − 5 y = 2 .
1. Vérifie que le point ( 4 ; 2 ) est sur D .
2. Détermine tous les points de D à coordonnées entières.
3. Combien ont une abscisse comprise entre 0 et 100 ?
4. Écris une fonction Python qui compte ces points en testant toutes les abscisses de 0 à 100 .Voir le corrigé 1. 12 − 10 = 2 .
2. 3 ( x − 4 ) = 5 ( y − 2 ) et PGCD ( 3 ; 5 ) = 1 : 5 ∣ x − 4 . Points ( 4 + 5 k ; 2 + 3 k ) , k ∈ Z .
3. 0 ⩽ 4 + 5 k ⩽ 100 ⟺ − 0 , 8 ⩽ k ⩽ 19 , 2 : k de 0 à 19 , 20 points .
4.
def compte():
c = 0
for x in range(101):
if (3*x - 2) % 5 == 0:
c = c + 1
return c
(y = 5 3 x − 2 doit être entier.)📘 Annales bac maths terminale 2027
Le livre pour préparer l'épreuve du bac
75 sujets types classés par chapitre, 3 bacs blancs et des corrigés avec la rédaction attendue.
Découvrir les annales → 🖨 Imprimer Exercice 15 type bac Un chiffrement affine On numérote les lettres de A = 0 à Z = 25 . Pour coder une lettre de rang x , on calcule le reste y de 7 x + 3 modulo 26 ; la lettre codée est celle de rang y .
1. Code la lettre M (rang 12 ).
2. Montre que 7 × 15 ≡ 1 [ 26 ] .
3. Montre que si y ≡ 7 x + 3 [ 26 ] , alors x ≡ 15 y + 7 [ 26 ] .
4. Décode la lettre J (rang 9 ). Deux lettres différentes peuvent-elles avoir le même code ?Voir le corrigé 1. 7 × 12 + 3 = 87 = 3 × 26 + 9 : M est codé J .
2. 105 = 4 × 26 + 1 .
3. On multiplie par 15 : 15 y ≡ 105 x + 45 ≡ x + 45 [ 26 ] , donc x ≡ 15 y − 45 ≡ 15 y + 7 [ 26 ] (car − 45 = − 2 × 26 + 7 ).
4. 15 × 9 + 7 = 142 = 5 × 26 + 12 : J se décode en M . Le décodage donne une seule lettre : deux lettres différentes ont des codes différents .🖨 Imprimer Exercice 16 type bac L'équation 17x − 6y = 1 1. Vérifie que ( 5 ; 14 ) est solution de 17 x − 6 y = 1 , puis résous cette équation dans Z 2 .
2. On cherche les entiers N tels que N ≡ 3 [ 17 ] et N ≡ 2 [ 6 ] . Montre que N = 3 + 17 x = 2 + 6 y avec 17 x − 6 y = − 1 .
3. Déduis-en que N ≡ 20 [ 102 ] .
4. Quel est le plus petit entier supérieur à 1 000 qui convient ?Voir le corrigé 1. 85 − 84 = 1 . 17 ( x − 5 ) = 6 ( y − 14 ) , PGCD ( 17 ; 6 ) = 1 : x = 5 + 6 k , y = 14 + 17 k .
2. N = 3 + 17 x et N = 2 + 6 y donnent 17 x − 6 y = − 1 .
3. Les solutions de 17 x − 6 y = − 1 sont les opposées : x = − 5 + 6 k . Donc N = 3 + 17 ( − 5 + 6 k ) = − 82 + 102 k , soit N ≡ 20 [ 102 ] .
4. 20 + 102 × 10 = 1 040 : 1 040 .
Les autres exercices de maths expertes
Annales du bac de maths corrigées
Questions fréquentes
Comment calculer un PGCD ? Avec l'algorithme d'Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, et ainsi de suite. Le PGCD est le dernier reste non nul.
Que dit le théorème de Bézout ? a et b sont premiers entre eux si et seulement s'il existe des entiers u et v tels que au + bv = 1. On trouve u et v en remontant l'algorithme d'Euclide.
Que dit le théorème de Gauss ? Si a divise bc et si a et b sont premiers entre eux, alors a divise c. Il sert à résoudre les équations diophantiennes ax + by = c.
Comment résoudre une équation diophantienne ax + by = c ? On vérifie que PGCD(a, b) divise c (sinon, pas de solution), on simplifie, on trouve une solution particulière, on soustrait les deux égalités et on conclut avec le théorème de Gauss.
Les exercices sont-ils gratuits ? Oui. Les 16 exercices et leurs corrigés sont gratuits, en ligne et en PDF à imprimer, sans inscription.