Karamö, le prof virtuelLeçon 21 sur 41
Arithmétique
Je sais calculer un PGCD et un PPCM, utiliser les théorèmes de Bézout et de Gauss, décomposer un entier en facteurs premiers et résoudre une équation ax + by = c dans ℤ.
- 2 h
- 5 exercices corrigés
- 1 schéma
- QCM de 5 questions
À la fin de la leçon, tu sauras :
- Calculer un PGCD par l'algorithme d'Euclide et par la décomposition en facteurs premiers
- Utiliser les théorèmes de Bézout et de Gauss
- Reconnaître un nombre premier et décomposer un entier en produit de facteurs premiers
- Résoudre dans ℤ² une équation du type ax + by = c
Avant de commencer : Les ensembles ℕ et ℤ : divisibilité, combinaisons linéaires, division euclidienne et congruences.
1Je découvre
Aïssatou aide son père, carreleur à Kankan, à préparer un chantier. Il doit recouvrir le sol d'une pièce rectangulaire de 360 cm sur 252 cm avec des carreaux carrés tous identiques, sans en découper aucun. Pour aller vite, il veut les plus grands carreaux possibles.
Le côté du carreau doit donc diviser 360 et diviser 252 : c'est un diviseur commun. Et on veut le plus grand. Aïssatou pourrait écrire tous les diviseurs de 360 (il y en a 24) et tous ceux de 252 (il y en a 18), puis chercher le plus grand qui apparaît dans les deux listes… C'est long, et avec des nombres plus grands, ce serait impossible à la main.
Son père lui montre une méthode vieille de plus de deux mille ans, due au mathématicien grec Euclide, qui donne la réponse en trois divisions seulement.
Comment trouver rapidement le plus grand diviseur commun de deux entiers, et à quoi sert-il pour résoudre des équations en nombres entiers ?
2Je comprends
1. Le PGCD et l'algorithme d'Euclide
Définition. Soient a et b deux entiers relatifs non tous deux nuls. Le PGCD de a et b (plus grand commun diviseur) est le plus grand entier naturel qui divise à la fois a et b. On le note PGCD(a ; b) ou a wedge b.
On a PGCD(a ; b) = PGCD(|a| ; |b|) ; on travaille donc avec des entiers naturels.
Propriété clé. Si a = bq + r (division euclidienne), alors PGCD(a ; b) = PGCD(b ; r).
En effet, tout diviseur commun de a et b divise r = a - bq, et tout diviseur commun de b et r divise a = bq + r : les diviseurs communs sont les mêmes.
Algorithme d'Euclide. On divise a par b, puis b par le reste, puis ce reste par le nouveau reste, et ainsi de suite. Les restes diminuent strictement, donc on finit par obtenir un reste nul. Le PGCD est le dernier reste non nul.
- 1360 = 252 × 1 + 108, donc PGCD(360 ; 252) = PGCD(252 ; 108).
- 2252 = 108 × 2 + 36, donc PGCD(252 ; 108) = PGCD(108 ; 36).
- 3108 = 36 × 3 + 0 : le reste est nul.
- 4Le dernier reste non nul est 36 : PGCD(360 ; 252) = 36.
Le père d'Aïssatou prendra donc des carreaux de 36 cm de côté : 360 ÷ 36 = 10 et 252 ÷ 36 = 7, soit 10 × 7 = 70 carreaux.
Propriété. Les diviseurs communs de a et b sont exactement les diviseurs de leur PGCD.
2. Nombres premiers entre eux et théorème de Bézout
Définition. Deux entiers a et b sont premiers entre eux si PGCD(a ; b) = 1 : leur seul diviseur commun positif est 1. Exemple : 8 et 15.
Identité de Bézout. Si d = PGCD(a ; b), il existe des entiers relatifs u et v tels que au + bv = d.
Théorème de Bézout. a et b sont premiers entre eux si et seulement si il existe des entiers relatifs u et v tels que
au + bv = 1.
Pour trouver u et v, on « remonte » l'algorithme d'Euclide.
Exemple
Montrer que 17 et 5 sont premiers entre eux et trouver u et v tels que 17u + 5v = 1.
Euclide : 17 = 5 × 3 + 2 ; 5 = 2 × 2 + 1 ; 2 = 1 × 2 + 0. Le PGCD vaut 1.
On remonte : 1 = 5 − 2 × 2, et 2 = 17 − 5 × 3.
Donc 1 = 5 − 2 × (17 − 5 × 3) = 5 − 2 × 17 + 6 × 5 = 7 × 5 − 2 × 17.
u = −2 et v = 7. Vérification : 17 × (−2) + 5 × 7 = −34 + 35 = 1.
Exemple
Montrer que, pour tout entier n, 2n + 1 et 3n + 2 sont premiers entre eux.
3 × (2n + 1) − 2 × (3n + 2) = 6n + 3 − 6n − 4 = −1, donc (2n + 1) × (−3) + (3n + 2) × 2 = 1.
D'après le théorème de Bézout, 2n + 1 et 3n + 2 sont premiers entre eux.
3. Le théorème de Gauss
Théorème de Gauss. Si a divise le produit bc et si a est premier avec b, alors a divise c.
Démonstration : comme PGCD(a ; b) = 1, il existe u, v avec au + bv = 1. En multipliant par c : acu + bcv = c. Or a divise acu et a divise bcv (car a mid bc), donc a divise leur somme c.
Conséquence. Si a et b sont premiers entre eux et divisent tous les deux n, alors ab divise n. Par exemple, un nombre divisible par 3 et par 4 est divisible par 12. (Attention : divisible par 4 et par 6 n'entraîne pas divisible par 24, car 4 et 6 ne sont pas premiers entre eux : pense à 12.)
4. Nombres premiers et décomposition
Définition. Un entier naturel p est premier s'il a exactement deux diviseurs positifs : 1 et lui-même. Les premiers nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… (1 n'est pas premier). Il existe une infinité de nombres premiers.
Test de primalité. Si n ≥ 2 n'est divisible par aucun nombre premier p tel que p2 ≤ n, alors n est premier.
Théorème fondamental. Tout entier n ≥ 2 se décompose en produit de facteurs premiers, et cette décomposition est unique (à l'ordre près).
PGCD et PPCM par la décomposition. Le PPCM de a et b est le plus petit multiple commun strictement positif.
- PGCD : produit des facteurs premiers communs, chacun avec le plus petit exposant.
- PPCM : produit de tous les facteurs premiers, chacun avec le plus grand exposant.
- Pour a et b positifs : PGCD(a ; b) × PPCM(a ; b) = a × b.
Exemple
Décomposer 360 et 252, puis calculer leur PGCD et leur PPCM.
360 = 2³ × 3² × 5 et 252 = 2² × 3² × 7.
PGCD = 2² × 3² = 36 (on retrouve le résultat d'Euclide).
PPCM = 2³ × 3² × 5 × 7 = 2 520.
Contrôle : 36 × 2 520 = 90 720 et 360 × 252 = 90 720.
Exemple
221 est-il premier ?
√221 ≈ 14,9 : on teste les nombres premiers 2, 3, 5, 7, 11, 13.
221 est impair ; 2 + 2 + 1 = 5 n'est pas divisible par 3 ; il ne finit ni par 0 ni par 5 ; 221 = 7 × 31 + 4 ; 221 = 11 × 20 + 1 ; mais 221 = 13 × 17.
221 n'est donc pas premier.
5. Les équations ax + by = c dans ℤ
Propriété. L'équation ax + by = c (d'inconnues x, y entiers) a des solutions si et seulement si PGCD(a ; b) divise c.
Méthode
Pour résoudre ax + by = c dans ℤ² (avec a et b premiers entre eux) :
- Je trouve une solution particulière (x₀ ; y₀), à vue ou en remontant Euclide.
- Je soustrais : a(x − x₀) + b(y − y₀) = 0, soit a(x − x₀) = −b(y − y₀).
- Comme b divise a(x − x₀) et que b est premier avec a, Gauss donne : b divise x − x₀, donc x = x₀ + bk.
- Je remplace pour trouver y = y₀ − ak (k ∈ ℤ).
- Je vérifie que ces couples sont bien solutions, puis j'écris l'ensemble S.
Exemple
Résoudre dans ℤ² l'équation 17x + 5y = 1.
Solution particulière (trouvée plus haut) : (−2 ; 7).
17x + 5y = 17 × (−2) + 5 × 7, donc 17(x + 2) = −5(y − 7).
5 divise 17(x + 2) et 5 est premier avec 17 : par Gauss, 5 divise x + 2, donc x = −2 + 5k.
Alors 17 × 5k = −5(y − 7), soit y − 7 = −17k, donc y = 7 − 17k.
Réciproque : 17(−2 + 5k) + 5(7 − 17k) = −34 + 85k + 35 − 85k = 1.
S = {(−2 + 5k ; 7 − 17k), k ∈ ℤ}.
3Je retiens
Je retiens
Si a = bq + r, alors PGCD(a ; b) = PGCD(b ; r). Euclide : le PGCD est le dernier reste non nul.
a et b premiers entre eux ⇔ PGCD(a ; b) = 1 ⇔ il existe u, v entiers tels que au + bv = 1 (Bézout).
Gauss : si a | bc et PGCD(a ; b) = 1, alors a | c.
Tout entier n ≥ 2 a une décomposition unique en facteurs premiers.
PGCD : facteurs communs, plus petits exposants ; PPCM : tous les facteurs, plus grands exposants ; PGCD × PPCM = ab.
ax + by = c a des solutions ⇔ PGCD(a ; b) divise c.
4Erreurs fréquentes
- Croire que 1 est un nombre premier : il n'a qu'un seul diviseur positif.
- Appliquer Gauss sans vérifier que les nombres sont premiers entre eux : 6 divise 4 × 3, mais 6 ne divise ni 4 ni 3.
- Conclure « PGCD = 1 » dès qu'on trouve au + bv = 2 : Bézout ne marche que pour 1 (au + bv = 2 prouve seulement que le PGCD divise 2).
- Oublier le paramètre k : une équation ax + by = c a une infinité de solutions, pas une seule.
5Je m’exerce
1Exercice 1
Calcule PGCD(1 071 ; 462) par l'algorithme d'Euclide.
Voir le corrigéCacher le corrigé
1 071 = 462 × 2 + 147 ; 462 = 147 × 3 + 21 ; 147 = 21 × 7 + 0.
Le dernier reste non nul est 21 : PGCD(1 071 ; 462) = 21.
2Exercice 2
Décompose 1 260 et 588 en produit de facteurs premiers, puis calcule leur PGCD et leur PPCM. Vérifie avec la relation PGCD × PPCM = ab.
Voir le corrigéCacher le corrigé
1 260 = 22 × 32 × 5 × 7 et 588 = 22 × 3 × 72.
PGCD = 22 × 3 × 7 = 84 et PPCM = 22 × 32 × 5 × 72 = 4 × 9 × 5 × 49 = 8 820.
Vérification : 84 × 8 820 = 740 880 et 1 260 × 588 = 740 880.
3Exercice 3
Les nombres 97 et 91 sont-ils premiers ? Justifie.
Voir le corrigéCacher le corrigé
√97 ≈ 9,8 : on teste 2, 3, 5 et 7. 97 est impair, 9 + 7 = 16 n'est pas multiple de 3, il ne finit ni par 0 ni par 5, et 97 = 7 × 13 + 6. Donc 97 est premier.
91 = 7 × 13 : 91 n'est pas premier.
4Exercice 4
a) Montre que 23 et 7 sont premiers entre eux et trouve deux entiers u et v tels que 23u + 7v = 1.
b) Un entier n est tel que 7 divise 23n. Que peux-tu dire de n ? Justifie.
Voir le corrigéCacher le corrigé
a) 23 = 7 × 3 + 2 ; 7 = 2 × 3 + 1 : le PGCD vaut 1, donc 23 et 7 sont premiers entre eux.
On remonte : 1 = 7 - 2 × 3 = 7 - 3(23 - 7 × 3) = 10 × 7 - 3 × 23.
Donc u = -3 et v = 10. Vérification : 23 × (-3) + 7 × 10 = -69 + 70 = 1.
b) 7 divise 23n et 7 est premier avec 23 : d'après le théorème de Gauss, 7 divise n.
5Exercice 5
(Type BAC) On considère l'équation (E) : 13x - 8y = 1, où x et y sont des entiers relatifs.
a) Vérifie que le couple (5 ; 8) est une solution de (E).
b) Résous l'équation (E).
c) Détermine les solutions de (E) telles que 0 < x < 30.
Voir le corrigéCacher le corrigé
a) 13 × 5 - 8 × 8 = 65 - 64 = 1 : (5 ; 8) est bien solution.
b) Si (x ; y) est solution, 13x - 8y = 13 × 5 - 8 × 8, donc 13(x - 5) = 8(y - 8).
8 divise 13(x - 5) et 8 est premier avec 13 (car PGCD(13 ; 8) = 1) : par Gauss, 8 divise x - 5, donc x = 5 + 8k avec k ∈ ℤ.
Alors 13 × 8k = 8(y - 8), donc y - 8 = 13k et y = 8 + 13k.
Réciproquement, 13(5 + 8k) - 8(8 + 13k) = 65 + 104k - 64 - 104k = 1.
S = {(5 + 8k ; 8 + 13k), k ∈ ℤ}.
c) 0 < 5 + 8k < 30 ⇔ -5 < 8k < 25 ⇔ -0,625 < k < 3,125, donc k ∈ {0, 1, 2, 3}.
Solutions : (5 ; 8), (13 ; 21), (21 ; 34) et (29 ; 47).
Cherche d’abord seul, sur ton cahier, puis ouvre le corrigé pour comparer.
6Je vérifie
Choisis une réponse pour chaque question : la correction s’affiche aussitôt.
Crée ton compte élève gratuit pour cocher les leçons terminées, suivre ta progression et gagner des points au QCM.
