PGCD, théorèmes de Bézout et de Gauss
Cours
On veut payer exactement \(100\) € avec des pièces de \(7\) et de \(11\) €, carreler une pièce avec des dalles carrées les plus grandes possibles, savoir quand deux comètes repasseront ensemble, ou chiffrer un message de façon qu'on puisse le déchiffrer. Toutes ces questions reposent sur le plus grand diviseur commun de deux entiers et sur deux théorèmes fondamentaux, ceux de Bézout et de Gauss. Avec ce chapitre, tu sauras :
- calculer un PGCD (plus grand commun diviseur) avec l'algorithme d'Euclide ;
- écrire le PGCD comme combinaison \(au + bv\) et reconnaître des entiers premiers entre eux ;
- utiliser le théorème de Gauss ;
- résoudre une congruence \(ax \equiv b \ [n]\), une équation \(ax + by = c\), et étudier un chiffrement affine.
1 PGCD et algorithme d'Euclide
Le plus grand entier qui divise à la fois \(a\) et \(b\) s'appelle leur PGCD.
Soient \(a\) et \(b\) deux entiers non tous deux nuls. Le PGCD de \(a\) et \(b\), noté \(\operatorname{PGCD}(a \,;\, b)\), est le plus grand entier naturel qui divise \(a\) et \(b\).
Si \(a = bq + r\) (division euclidienne, \(b \ne 0\)), alors \(\operatorname{PGCD}(a \,;\, b) = \operatorname{PGCD}(b \,;\, r)\). Algorithme d'Euclide : on remplace \((a \,;\, b)\) par \((b \,;\, r)\) et on recommence ; le dernier reste non nul est le PGCD.
L'idée en une phrase : \(a\), \(b\) et \(b\), \(r\) ont exactement les mêmes diviseurs communs.
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — Dans un sens. Si \(d\) divise \(a\) et \(b\), il divise \(r = a - bq\) (combinaison linéaire).
Étape 2 — Dans l'autre. Si \(d\) divise \(b\) et \(r\), il divise \(a = bq + r\).
Étape 3 — Conclure. Les deux couples ont les mêmes diviseurs communs, donc le même plus grand. Les restes diminuent strictement, donc l'algorithme s'arrête ; au dernier pas, \(\operatorname{PGCD}(r_k \,;\, 0) = r_k\) ✓.
Étape 1. \(1\,071 = 462 \times 2 + 147\).
Étape 2. \(462 = 147 \times 3 + 21\).
Étape 3. \(147 = 21 \times 7 + 0\).
Conclusion : le dernier reste non nul est \(21\) : \(\boxed{\operatorname{PGCD}(1\,071 \,;\, 462) = 21}\).
🔍 Vérification : \(1\,071 = 21 \times 51\) et \(462 = 21 \times 22\), avec \(51\) et \(22\) sans diviseur commun autre que \(1\) ✓.
- ❌ Donner le dernier reste, qui vaut \(0\). ✅ C'est le dernier reste non nul.
- ❌ Confondre PGCD et produit des facteurs communs « au hasard ». ✅ L'algorithme d'Euclide donne la réponse sans décomposer.
Calcule \(\operatorname{PGCD}(120 \,;\, 84)\) avec l'algorithme d'Euclide.
Voir la réponseMasquer la réponse
\(120 = 84 \times 1 + 36\) ; \(84 = 36 \times 2 + 12\) ; \(36 = 12 \times 3 + 0\). Le PGCD est \(12\).
\(\operatorname{PGCD}(a \,;\, b) = \operatorname{PGCD}(b \,;\, r)\) ; Euclide : dernier reste non nul.
2 Identité et théorème de Bézout
Le PGCD peut toujours s'écrire comme une combinaison de \(a\) et \(b\) à coefficients entiers.
Pour tous entiers \(a\) et \(b\) non tous deux nuls, il existe des entiers \(u\) et \(v\) tels que \[au + bv = \operatorname{PGCD}(a \,;\, b).\]
L'idée en une phrase : on considère le plus petit entier strictement positif de la forme \(au + bv\), et on montre que c'est le PGCD.
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — Le plus petit. L'ensemble des entiers \(au + bv > 0\) n'est pas vide (il contient \(|a|\) ou \(|b|\)) : il a un plus petit élément \(d = au_0 + bv_0\).
Étape 2 — \(d\) divise \(a\). On divise : \(a = dq + r\) avec \(0 \leqslant r < d\). Alors \(r = a - dq = a(1 - qu_0) + b(-qv_0)\) est de la même forme ; s'il était strictement positif, il serait plus petit que \(d\) : impossible. Donc \(r = 0\) et \(d \mid a\). De même, \(d \mid b\).
Étape 3 — \(d\) est le plus grand. Tout diviseur commun de \(a\) et \(b\) divise \(au_0 + bv_0 = d\), donc lui est inférieur ou égal. Ainsi \(d = \operatorname{PGCD}(a \,;\, b)\) ✓.
\(a\) et \(b\) sont premiers entre eux si \(\operatorname{PGCD}(a \,;\, b) = 1\).
\(a\) et \(b\) sont premiers entre eux si, et seulement si, il existe des entiers \(u\) et \(v\) tels que \(au + bv = 1\).
On écrit les divisions d'Euclide, on exprime le dernier reste non nul, puis on remplace successivement les restes précédents.
Étape 1 — Le dernier reste. \(21 = 462 - 3 \times 147\).
Étape 2 — Remplacer \(147\). \(147 = 1\,071 - 2 \times 462\), donc \(21 = 462 - 3(1\,071 - 2 \times 462) = 7 \times 462 - 3 \times 1\,071\).
Conclusion : \(\boxed{1\,071 \times (-3) + 462 \times 7 = 21}\).
🔍 Vérification : \(-3\,213 + 3\,234 = 21\) ✓.
- ❌ Croire que \(u\) et \(v\) sont uniques. ✅ Il y en a une infinité (par exemple, on peut ajouter \(b\) à \(u\) et retrancher \(a\) à \(v\) quand le PGCD vaut \(1\)).
- ❌ Conclure « premiers entre eux » de \(au + bv = 3\). ✅ Seul \(au + bv = 1\) le permet.
Montre que \(2n + 1\) et \(3n + 1\) sont premiers entre eux pour tout entier \(n\).
Voir la réponseMasquer la réponse
\(3(2n + 1) - 2(3n + 1) = 6n + 3 - 6n - 2 = 1\) : d'après Bézout, ils sont premiers entre eux.
\(\operatorname{PGCD}(a \,;\, b) = au + bv\) ; premiers entre eux \(\iff au + bv = 1\) possible ; on trouve \(u\), \(v\) en remontant l'algorithme d'Euclide.
3 Le théorème de Gauss
Quand un nombre divise un produit sans avoir de facteur commun avec l'un des deux termes, il divise l'autre.
Si \(a\) divise \(bc\) et si \(a\) et \(b\) sont premiers entre eux, alors \(a\) divise \(c\). Conséquence : si \(a\) et \(b\) divisent \(c\) et sont premiers entre eux, alors \(ab\) divise \(c\).
L'idée en une phrase : on multiplie l'identité de Bézout par \(c\).
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — Bézout. \(a\) et \(b\) premiers entre eux : il existe \(u\), \(v\) avec \(au + bv = 1\).
Étape 2 — Multiplier par \(c\). \(acu + bcv = c\).
Étape 3 — Conclure. \(a\) divise \(acu\) et divise \(bc\) (donc \(bcv\)) : il divise leur somme \(c\) ✓.
Conséquence. \(c = ak\) ; \(b\) divise \(ak\) et est premier avec \(a\), donc \(b \mid k\) (Gauss) : \(k = bk'\) et \(c = abk'\) ✓.
On sait que \(7\) divise \(4n\). Montrer que \(7\) divise \(n\).
Étape 1 — Vérifier l'hypothèse. \(\operatorname{PGCD}(7 \,;\, 4) = 1\).
Étape 2 — Appliquer. \(7 \mid 4 \times n\) et \(7\) est premier avec \(4\), donc \(7 \mid n\) (Gauss).
🔍 Vérification : \(4 \times 21 = 84 = 7 \times 12\), et \(21\) est bien multiple de \(7\) ✓.
- ❌ « \(6\) divise \(4 \times 3\), donc \(6\) divise \(3\). » ✅ Faux : \(6\) et \(4\) ne sont pas premiers entre eux, Gauss ne s'applique pas.
- ❌ « \(4 \mid n\) et \(6 \mid n\), donc \(24 \mid n\). » ✅ \(4\) et \(6\) ne sont pas premiers entre eux (\(n = 12\) est un contre-exemple).
Un entier \(n\) est divisible par \(3\) et par \(4\). Est-il divisible par \(12\) ?
Voir la réponseMasquer la réponse
Oui : \(3\) et \(4\) sont premiers entre eux et divisent \(n\), donc \(3 \times 4 = 12\) divise \(n\).
Gauss : \(a \mid bc\) et \(\operatorname{PGCD}(a \,;\, b) = 1 \Rightarrow a \mid c\) ; toujours vérifier que les nombres sont premiers entre eux.
4 Congruences ax ≡ b [n] et inverse modulo n
Au chapitre précédent, on ne savait pas « diviser » une congruence. Bézout permet de le faire quand \(a\) est premier avec \(n\).
Un inverse de \(a\) modulo \(n\) est un entier \(a'\) tel que \(aa' \equiv 1 \ [n]\).
\(a\) a un inverse modulo \(n\) si, et seulement si, \(a\) et \(n\) sont premiers entre eux. Dans ce cas, \(ax \equiv b \ [n] \iff x \equiv a'b \ [n]\).
L'idée en une phrase : \(aa' \equiv 1 \ [n]\) s'écrit \(aa' + nk = 1\), c'est exactement Bézout.
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — Existence. Si \(\operatorname{PGCD}(a \,;\, n) = 1\), Bézout donne \(au + nv = 1\), donc \(au \equiv 1 \ [n]\) : \(u\) est un inverse. Réciproquement, \(aa' - 1 = nk\) donne \(aa' - nk = 1\).
Étape 2 — Résoudre. Si \(ax \equiv b\), en multipliant par \(a'\) : \(x \equiv a'ax \equiv a'b \ [n]\). Réciproquement, si \(x \equiv a'b\), alors \(ax \equiv aa'b \equiv b\) ✓.
Étape 1 — Un inverse de \(3\). \(3 \times 5 = 15 \equiv 1 \ [7]\) : l'inverse est \(5\).
Étape 2 — Multiplier. \(x \equiv 5 \times 2 = 10 \equiv 3 \ [7]\).
Conclusion : les solutions sont les entiers \(\boxed{x = 3 + 7k,\ k \in \mathbb{Z}}\).
🔍 Vérification : \(3 \times 3 = 9 \equiv 2 \ [7]\) ✓.
- ❌ Diviser par \(3\) « comme dans \(\mathbb{R}\) ». ✅ On multiplie par l'inverse modulo \(n\).
- ❌ Chercher un inverse de \(6\) modulo \(9\). ✅ \(\operatorname{PGCD}(6 \,;\, 9) = 3\) : il n'y en a pas.
Trouve l'inverse de \(7\) modulo \(26\).
Voir la réponseMasquer la réponse
\(26 = 7 \times 3 + 5\), \(7 = 5 + 2\), \(5 = 2 \times 2 + 1\) ; en remontant, \(1 = 26 \times 3 - 7 \times 11\), donc \(7 \times (-11) \equiv 1 \ [26]\) et l'inverse est \(-11 \equiv 15\) (vérification : \(7 \times 15 = 105 = 4 \times 26 + 1\)).
Inverse de \(a\) modulo \(n\) ⇔ \(\operatorname{PGCD}(a \,;\, n) = 1\) ; \(ax \equiv b \iff x \equiv a'b\).
5 Équations diophantiennes ax + by = c
On cherche les couples d'entiers \((x \,;\, y)\) tels que \(ax + by = c\).
L'équation \(ax + by = c\) a des solutions entières si, et seulement si, \(\operatorname{PGCD}(a \,;\, b)\) divise \(c\).
- vérifier que \(d = \operatorname{PGCD}(a \,;\, b)\) divise \(c\), puis tout diviser par \(d\) ;
- trouver une solution particulière \((x_0 \,;\, y_0)\) (Bézout multiplié par \(c\), ou essais) ;
- soustraire : \(a(x - x_0) = -b(y - y_0)\), puis appliquer Gauss ;
- conclure : \(x = x_0 + bk\), \(y = y_0 - ak\), \(k \in \mathbb{Z}\) (avec \(a\) et \(b\) premiers entre eux).
Étape 1 — Une solution particulière. \(5 \times (-1) + 3 \times 2 = 1\) : \((x_0 \,;\, y_0) = (-1 \,;\, 2)\).
Étape 2 — Soustraire. Si \(5x + 3y = 1\), alors \(5(x + 1) + 3(y - 2) = 0\), soit \(5(x + 1) = -3(y - 2)\).
Étape 3 — Gauss. \(3\) divise \(5(x + 1)\) et est premier avec \(5\), donc \(3 \mid x + 1\) : \(x + 1 = 3k\). En remplaçant : \(5 \times 3k = -3(y - 2)\), d'où \(y - 2 = -5k\).
Conclusion : \(\boxed{x = -1 + 3k,\ y = 2 - 5k,\ k \in \mathbb{Z}}\) (et réciproquement, ces couples conviennent).
🔍 Vérification : \(5(-1 + 3k) + 3(2 - 5k) = -5 + 15k + 6 - 15k = 1\) ✓.
- ❌ Donner seulement la solution particulière. ✅ L'équation a une infinité de solutions, décrites par un paramètre \(k\).
- ❌ Oublier la réciproque. ✅ On vérifie que les couples trouvés sont bien solutions.
L'équation \(4x + 6y = 5\) a-t-elle des solutions entières ?
Voir la réponseMasquer la réponse
\(\operatorname{PGCD}(4 \,;\, 6) = 2\) ne divise pas \(5\) : aucune solution entière (le membre de gauche est toujours pair).
Solutions entières ⇔ \(\operatorname{PGCD}(a \,;\, b) \mid c\) ; solution particulière + Gauss → \(x = x_0 + bk\), \(y = y_0 - ak\).
Quiz du cours
Tu as lu le cours ? Vérifie en 7 questions que tu as retenu l’essentiel. Chaque réponse est corrigée tout de suite, sans chronomètre.
Combien vaut \(\operatorname{PGCD}(1\,071 \,;\, 462)\) ?
Réponse attendue : \(21\)
Euclide : \(1\,071 = 462 \times 2 + 147\), \(462 = 147 \times 3 + 21\), \(147 = 21 \times 7\).
Que permet de conclure l'égalité \(5 \times (-1) + 3 \times 2 = 1\) ?
Théorème de Bézout : s'il existe \(u\), \(v\) avec \(au + bv = 1\), alors \(a\) et \(b\) sont premiers entre eux.
Vrai ou faux : si \(6\) divise \(4n\), alors \(6\) divise \(n\).
\(6\) et \(4\) ne sont pas premiers entre eux : Gauss ne s'applique pas. Contre-exemple : \(n = 3\), \(4n = 12\).
Un entier est divisible par \(3\) et par \(4\). Par quel nombre est-il forcément divisible ?
\(3\) et \(4\) sont premiers entre eux : leur produit \(12\) divise l'entier.
Quel est l'inverse de \(3\) modulo \(7\) (entre \(0\) et \(6\)) ?
Réponse attendue : \(5\)
\(3 \times 5 = 15 = 2 \times 7 + 1\), donc \(3 \times 5 \equiv 1 \ [7]\).
Revoir dans le cours : 4. Congruences ax ≡ b [n] et inverse modulo n
Quelles sont les solutions de \(3x \equiv 2 \ [7]\) ?
On multiplie par l'inverse \(5\) : \(x \equiv 10 \equiv 3 \ [7]\).
Revoir dans le cours : 4. Congruences ax ≡ b [n] et inverse modulo n
L'équation \(4x + 6y = 5\) a-t-elle des solutions entières ?
\(ax + by = c\) a des solutions entières si, et seulement si, \(\operatorname{PGCD}(a \,;\, b)\) divise \(c\).
Revoir dans le cours : 5. Équations diophantiennes ax + by = c
À revoir dans le cours :
Fiche mémo
L’essentiel du chapitre, à relire avant un contrôle.
L'essentiel
| Notion | À savoir |
|---|---|
| PGCD | plus grand diviseur commun ; \(\operatorname{PGCD}(a \,;\, b) = \operatorname{PGCD}(b \,;\, r)\) |
| Euclide | divisions successives ; dernier reste non nul |
| Identité de Bézout | \(au + bv = \operatorname{PGCD}(a \,;\, b)\) |
| Premiers entre eux | \(\operatorname{PGCD} = 1 \iff au + bv = 1\) possible |
| Gauss | \(a \mid bc\), \(\operatorname{PGCD}(a \,;\, b) = 1 \Rightarrow a \mid c\) |
| Conséquence | \(a \mid c\), \(b \mid c\), \(\operatorname{PGCD}(a \,;\, b) = 1 \Rightarrow ab \mid c\) |
| Inverse modulo \(n\) | existe \(\iff \operatorname{PGCD}(a \,;\, n) = 1\) ; \(ax \equiv b \iff x \equiv a'b\) |
| \(ax + by = c\) | solutions \(\iff \operatorname{PGCD} \mid c\) ; \(x = x_0 + bk\), \(y = y_0 - ak\) |
Pièges à éviter
- Le PGCD est le dernier reste non nul.
- Gauss exige des nombres premiers entre eux.
- Ne pas diviser une congruence : multiplier par un inverse.
- Une équation diophantienne a une infinité de solutions (ou aucune).
Contrôle demain ? Prépare ton plan de révision de 30 minutes sur ce chapitre →
Niveau 1Facile (Exercices 1 à 11)
Calcule \(\operatorname{PGCD}(84 \,;\, 36)\) et \(\operatorname{PGCD}(48 \,;\, 180)\).
Voir la correction›
lister les diviseurs communs, ou utiliser Euclide.
\(84 = 36 \times 2 + 12\) et \(36 = 12 \times 3\) : \(\boxed{\operatorname{PGCD}(84 \,;\, 36) = 12}\). \(180 = 48 \times 3 + 36\), \(48 = 36 + 12\), \(36 = 12 \times 3\) : \(\boxed{\operatorname{PGCD}(48 \,;\, 180) = 12}\).
🔍 Vérification : \(84 = 12 \times 7\) et \(36 = 12 \times 3\) ✓
Calcule \(\operatorname{PGCD}(1\,071 \,;\, 462)\) en détaillant les étapes.
Voir la correction›
divisions successives.
\(1\,071 = 462 \times 2 + 147\) ; \(462 = 147 \times 3 + 21\) ; \(147 = 21 \times 7 + 0\). \(\boxed{\operatorname{PGCD} = 21}\).
🔍 Vérification : voir l'exemple du cours ✓
Les entiers \(35\) et \(18\) sont-ils premiers entre eux ? Et \(21\) et \(49\) ?
Voir la correction›
chercher un diviseur commun autre que \(1\).
\(35 = 5 \times 7\) et \(18 = 2 \times 3^2\) : aucun facteur commun, premiers entre eux. \(21 = 3 \times 7\) et \(49 = 7^2\) : PGCD (plus grand commun diviseur) \(= 7\), pas premiers entre eux.
🔍 Vérification : \(35 = 18 + 17\), \(18 = 17 + 1\) : Euclide donne \(1\) ✓
Vérifie que \(5 \times (-1) + 3 \times 2 = 1\). Que peut-on en conclure pour \(5\) et \(3\) ?
Voir la correction›
théorème de Bézout.
\(-5 + 6 = 1\) ✓. Il existe \(u = -1\) et \(v = 2\) avec \(5u + 3v = 1\) : \(\boxed{5 \text{ et } 3 \text{ sont premiers entre eux}}\).
🔍 Vérification : c'est évident, \(3\) et \(5\) étant premiers distincts ✓
Trouve des entiers \(u\) et \(v\) tels que \(7u + 3v = 1\).
Voir la correction›
essais ou Euclide remonté.
\(7 \times 1 + 3 \times (-2) = 1\) : \(\boxed{u = 1,\ v = -2}\).
🔍 Vérification : \(7 - 6 = 1\) ✓
On sait que \(7\) divise \(4n\). Montre que \(7\) divise \(n\).
Voir la correction›
Gauss, avec \(\operatorname{PGCD}(7 \,;\, 4) = 1\).
\(7 \mid 4n\) et \(7\) premier avec \(4\), donc \(\boxed{7 \mid n}\).
🔍 Vérification : \(n = 7\) : \(4n = 28\) ✓
Trouve l'inverse de \(3\) modulo \(7\).
Voir la correction›
chercher \(a'\) avec \(3a' \equiv 1 \ [7]\).
\(3 \times 5 = 15 = 2 \times 7 + 1\) : l'inverse est \(\boxed{5}\).
🔍 Vérification : \(15 \equiv 1 \ [7]\) ✓
Résous \(3x \equiv 2 \ [7]\).
Voir la correction›
multiplier par l'inverse \(5\).
\(x \equiv 5 \times 2 = 10 \equiv 3 \ [7]\) : \(\boxed{x = 3 + 7k,\ k \in \mathbb{Z}}\).
🔍 Vérification : \(3 \times 10 = 30 = 4 \times 7 + 2\) ✓ (avec \(x = 10\))
Montre que l'équation \(2x + 4y = 7\) n'a pas de solution entière.
Voir la correction›
condition \(\operatorname{PGCD} \mid c\).
\(\operatorname{PGCD}(2 \,;\, 4) = 2\) ne divise pas \(7\) : pas de solution. (En effet, \(2x + 4y\) est toujours pair et \(7\) est impair.)
🔍 Vérification : parité ✓
Un entier \(n\) est divisible par \(3\) et par \(4\). Montre qu'il est divisible par \(12\).
Voir la correction›
conséquence du théorème de Gauss.
\(3 \mid n\), \(4 \mid n\) et \(\operatorname{PGCD}(3 \,;\, 4) = 1\), donc \(3 \times 4 = 12\) divise \(n\) ✓.
🔍 Vérification : \(n = 24\) : divisible par \(3\), par \(4\), et par \(12\) ✓
Montre que deux entiers consécutifs \(n\) et \(n + 1\) sont toujours premiers entre eux.
Voir la correction›
Bézout.
\((n + 1) \times 1 + n \times (-1) = 1\) : \(\boxed{n \text{ et } n + 1 \text{ sont premiers entre eux}}\).
🔍 Vérification : un diviseur commun divise leur différence, \(1\) ✓
Niveau 2Intermédiaire (Exercices 12 à 24)
a) Calcule \(\operatorname{PGCD}(252 \,;\, 198)\) avec l'algorithme d'Euclide.
b) Trouve des entiers \(u\) et \(v\) tels que \(252u + 198v = \operatorname{PGCD}(252 \,;\, 198)\).
Voir la correction›
Euclide, puis remontée.
a) \(252 = 198 + 54\) ; \(198 = 54 \times 3 + 36\) ; \(54 = 36 + 18\) ; \(36 = 18 \times 2\). \(\boxed{\operatorname{PGCD} = 18}\).
b) \(18 = 54 - 36 = 54 - (198 - 3 \times 54) = 4 \times 54 - 198 = 4(252 - 198) - 198 = 4 \times 252 - 5 \times 198\). \(\boxed{u = 4,\ v = -5}\).
🔍 Vérification : \(1\,008 - 990 = 18\) ✓
Résous dans \(\mathbb{Z}^2\) l'équation \(5x + 3y = 1\).
Voir la correction›
solution particulière, puis Gauss.
Voir l'exemple du cours : \(\boxed{x = -1 + 3k,\ y = 2 - 5k,\ k \in \mathbb{Z}}\).
🔍 Vérification : \(k = 1\) : \((2 \,;\, -3)\), et \(10 - 9 = 1\) ✓
Résous dans \(\mathbb{Z}^2\) l'équation \(11x - 7y = 1\).
Voir la correction›
même démarche.
\(11 \times 2 - 7 \times 3 = 1\) : \((2 \,;\, 3)\) est solution. Si \(11x - 7y = 1\), alors \(11(x - 2) = 7(y - 3)\) ; \(7\) divise \(11(x - 2)\) et est premier avec \(11\), donc \(x - 2 = 7k\), puis \(y - 3 = 11k\).
\(\boxed{x = 2 + 7k,\ y = 3 + 11k,\ k \in \mathbb{Z}}\).
🔍 Vérification : \(11(2 + 7k) - 7(3 + 11k) = 22 - 21 = 1\) ✓
a) Vérifie que \(7 \times (-5) + 12 \times 3 = 1\).
b) Résous dans \(\mathbb{Z}^2\) l'équation \(7x + 12y = 3\).
Voir la correction›
Bézout multiplié par \(3\).
a) \(-35 + 36 = 1\) ✓.
b) En multipliant par \(3\) : \(7 \times (-15) + 12 \times 9 = 3\). Si \(7x + 12y = 3\), alors \(7(x + 15) = -12(y - 9)\) ; Gauss donne \(x + 15 = 12k\) et \(y - 9 = -7k\).
\(\boxed{x = -15 + 12k,\ y = 9 - 7k,\ k \in \mathbb{Z}}\).
🔍 Vérification : \(k = 1\) : \((-3 \,;\, 2)\), et \(-21 + 24 = 3\) ✓
Trouve l'inverse de \(7\) modulo \(26\), à l'aide de l'algorithme d'Euclide.
Voir la correction›
Euclide remonté.
\(26 = 7 \times 3 + 5\) ; \(7 = 5 \times 1 + 2\) ; \(5 = 2 \times 2 + 1\). Donc \(1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7\).
\(7 \times (-11) \equiv 1 \ [26]\) : l'inverse est \(-11 \equiv \boxed{15}\).
🔍 Vérification : \(7 \times 15 = 105 = 4 \times 26 + 1\) ✓
On numérote les lettres de \(A = 0\) à \(Z = 25\) et on chiffre la lettre de rang \(x\) par celle de rang \(y \equiv 7x + 3 \ [26]\).
a) Chiffre les lettres A et M.
b) Avec l'exercice 16, exprime \(x\) en fonction de \(y\) pour déchiffrer.
Voir la correction›
appliquer la formule ; inverser avec \(15\).
a) A (\(0\)) : \(y = 3\), soit D. M (\(12\)) : \(7 \times 12 + 3 = 87 = 3 \times 26 + 9\), soit J.
b) \(y \equiv 7x + 3 \iff 7x \equiv y - 3 \iff x \equiv 15(y - 3) \ [26]\).
🔍 Vérification : J (\(9\)) : \(15 \times 6 = 90 = 3 \times 26 + 12\) → M ✓
Résous \(4x \equiv 6 \ [10]\) (on pourra se ramener à une congruence modulo \(5\)).
Voir la correction›
\(4x - 6 = 10k\) revient à \(2x - 3 = 5k\).
\(4x \equiv 6 \ [10] \iff 2x \equiv 3 \ [5]\). L'inverse de \(2\) modulo \(5\) est \(3\) (\(2 \times 3 = 6 \equiv 1\)), donc \(x \equiv 9 \equiv 4 \ [5]\).
\(\boxed{x \equiv 4 \text{ ou } x \equiv 9 \ [10]}\).
🔍 Vérification : \(4 \times 4 = 16 \equiv 6\) et \(4 \times 9 = 36 \equiv 6 \ [10]\) ✓
Un fermier remplit exactement \(100\) œufs dans des boîtes de \(7\) et de \(11\) œufs, toutes pleines. Combien de boîtes de chaque sorte utilise-t-il ?
Voir la correction›
\(7x + 11y = 100\) avec \(x\), \(y\) entiers positifs.
Modulo \(7\) : \(11y \equiv 100\), soit \(4y \equiv 2 \ [7]\). L'inverse de \(4\) modulo \(7\) est \(2\), donc \(y \equiv 4 \ [7]\). Avec \(11y \leqslant 100\), \(y \leqslant 9\) : \(y = 4\), puis \(7x = 100 - 44 = 56\), \(x = 8\).
\(\boxed{8 \text{ boîtes de } 7 \text{ et } 4 \text{ boîtes de } 11}\) (seule possibilité).
🔍 Vérification : \(56 + 44 = 100\) ✓
a) Montre que \(\operatorname{PGCD}(a \,;\, b) = \operatorname{PGCD}(b \,;\, a - b)\).
b) Calcule \(\operatorname{PGCD}(2\,026 \,;\, 2\,024)\).
Voir la correction›
mêmes diviseurs communs.
a) Un diviseur commun de \(a\) et \(b\) divise \(a - b\) ; un diviseur commun de \(b\) et \(a - b\) divise \((a - b) + b = a\). Les deux couples ont les mêmes diviseurs communs, donc le même PGCD ✓.
b) \(\operatorname{PGCD}(2\,026 \,;\, 2\,024) = \operatorname{PGCD}(2\,024 \,;\, 2) = \boxed{2}\).
🔍 Vérification : les deux nombres sont pairs, et leur différence est \(2\) ✓
Montre que \(2n + 1\) et \(3n + 1\) sont premiers entre eux pour tout entier naturel \(n\).
Voir la correction›
combinaison égale à \(1\).
\(3(2n + 1) - 2(3n + 1) = 1\) : d'après Bézout, \(\boxed{\operatorname{PGCD}(2n + 1 \,;\, 3n + 1) = 1}\).
🔍 Vérification : \(n = 4\) : \(9\) et \(13\) sont premiers entre eux ✓
On sait que \(15\) divise \(4x\). Montre que \(15\) divise \(x\).
Voir la correction›
Gauss avec \(\operatorname{PGCD}(15 \,;\, 4) = 1\).
\(15 \mid 4x\) et \(15\) premier avec \(4\), donc \(\boxed{15 \mid x}\).
🔍 Vérification : \(x = 15\) : \(4x = 60 = 15 \times 4\) ✓
Montre que la congruence \(6x \equiv 4 \ [9]\) n'a pas de solution.
Voir la correction›
\(6x - 4\) devrait être un multiple de \(9\), donc de \(3\).
\(6x \equiv 4 \ [9]\) donnerait \(6x - 4 = 9k\), puis \(4 = 6x - 9k = 3(2x - 3k)\) : \(3\) diviserait \(4\), impossible. Pas de solution ✓.
🔍 Vérification : \(6x \bmod 9\) ne prend que les valeurs \(0\), \(6\), \(3\) ✓
Deux roues dentées de \(24\) et \(36\) dents tournent ensemble. Au départ, deux dents repérées sont en contact. Au bout de combien de tours de chaque roue se retrouvent-elles en contact pour la première fois ?
Voir la correction›
le nombre de dents parcourues doit être un multiple commun de \(24\) et \(36\).
On cherche le plus petit multiple commun : \(24 = 2^3 \times 3\) et \(36 = 2^2 \times 3^2\), donc \(72\). La première roue fait \(\dfrac{72}{24} = \boxed{3 \text{ tours}}\) et la seconde \(\dfrac{72}{36} = \boxed{2 \text{ tours}}\).
🔍 Vérification : \(\dfrac{24 \times 36}{\operatorname{PGCD}(24 \,;\, 36)} = \dfrac{864}{12} = 72\) ✓
Niveau 3Difficile/Expert (Exercices 25 à 30)
Rédige la démonstration de l'identité de Bézout en considérant le plus petit entier strictement positif de la forme \(au + bv\).
Voir la correction›
voir la démonstration de la partie 2.
On note \(d = au_0 + bv_0\) le plus petit entier strictement positif de cette forme (il existe : l'ensemble contient \(|a|\) ou \(|b|\)). La division de \(a\) par \(d\) donne un reste \(r = a - qd\), encore de la forme \(au + bv\), avec \(0 \leqslant r < d\) : par minimalité, \(r = 0\), donc \(d \mid a\) ; de même \(d \mid b\). Tout diviseur commun divise \(d\), donc \(d\) est le plus grand : \(d = \operatorname{PGCD}(a \,;\, b)\) ✓.
🔍 Vérification : avec \(a = 1\,071\) et \(b = 462\), on trouve bien \(21 = 1\,071 \times (-3) + 462 \times 7\) ✓
Démontre le théorème de Gauss à partir du théorème de Bézout, puis sa conséquence : si \(a \mid c\), \(b \mid c\) et \(\operatorname{PGCD}(a \,;\, b) = 1\), alors \(ab \mid c\).
Voir la correction›
voir la démonstration de la partie 3.
\(au + bv = 1\), donc \(acu + bcv = c\) ; \(a\) divise les deux termes, donc \(c\). Conséquence : \(c = ak\), \(b \mid ak\) avec \(b\) premier avec \(a\), donc \(b \mid k\) et \(ab \mid c\) ✓.
🔍 Vérification : contre-exemple sans l'hypothèse : \(4 \mid 2 \times 6\) mais \(4 \nmid 6\) (car \(\operatorname{PGCD}(4 \,;\, 2) = 2\)) ✓
Résous dans \(\mathbb{Z}^2\) l'équation \(15x - 21y = 6\).
Voir la correction›
diviser par \(\operatorname{PGCD}(15 \,;\, 21) = 3\).
\(15x - 21y = 6 \iff 5x - 7y = 2\). Or \(5 \times 3 - 7 \times 2 = 1\), donc \((6 \,;\, 4)\) est solution. Gauss : \(5(x - 6) = 7(y - 4)\) donne \(x - 6 = 7k\), \(y - 4 = 5k\).
\(\boxed{x = 6 + 7k,\ y = 4 + 5k,\ k \in \mathbb{Z}}\).
🔍 Vérification : \(15 \times 6 - 21 \times 4 = 90 - 84 = 6\) ✓
Trouve tous les entiers \(n\) tels que \(n \equiv 2 \ [3]\) et \(n \equiv 3 \ [5]\).
Voir la correction›
tester les entiers de \(0\) à \(14\) (car \(3 \times 5 = 15\)), puis généraliser.
\(n \equiv 3 \ [5]\) : \(3, 8, 13\). Parmi eux, \(8 \equiv 2 \ [3]\). Si \(n\) et \(8\) vérifient les deux conditions, \(n - 8\) est divisible par \(3\) et par \(5\), premiers entre eux, donc par \(15\) : \(\boxed{n = 8 + 15k,\ k \in \mathbb{Z}}\).
🔍 Vérification : \(23 = 3 \times 7 + 2 = 5 \times 4 + 3\) ✓
Deux comètes ont des périodes de \(6\) ans et de \(15\) ans. Elles ont été visibles ensemble en 2026. En quelle année le seront-elles de nouveau ensemble pour la première fois ?
Voir la correction›
plus petit multiple commun de \(6\) et \(15\).
\(6 = 2 \times 3\) et \(15 = 3 \times 5\) : le plus petit multiple commun est \(30\). Prochaine apparition commune : \(\boxed{2056}\).
🔍 Vérification : \(30 = 6 \times 5 = 15 \times 2\) ✓
On utilise le chiffrement affine de l'exercice 17 : \(y \equiv 7x + 3 \ [26]\).
a) Chiffre le mot MATHS.
b) Déchiffre le message JDGAZ.
Voir la correction›
chiffrer avec \(y \equiv 7x + 3\), déchiffrer avec \(x \equiv 15(y - 3)\).
a) M (\(12\)) → \(87 \equiv 9\) (J) ; A (\(0\)) → \(3\) (D) ; T (\(19\)) → \(136 \equiv 6\) (G) ; H (\(7\)) → \(52 \equiv 0\) (A) ; S (\(18\)) → \(129 \equiv 25\) (Z). \(\boxed{\text{JDGAZ}}\).
b) On retrouve \(\boxed{\text{MATHS}}\) : par exemple G (\(6\)) → \(15 \times 3 = 45 \equiv 19\) (T) et Z (\(25\)) → \(15 \times 22 = 330 \equiv 18\) (S).
🔍 Vérification : le déchiffrement est possible car \(7\) est premier avec \(26\) (il a un inverse) ✓
Un avis sur ce chapitre ? Donne-le en quelques mots