Maths Expertes · Math@mine
Un boulanger vend des pains par boîtes de 7 ou de 11. Peut-il préparer exactement 58 pains ? Exactement 57 ? Pour quelles quantités \(n\) est-ce possible en général ?
Euclide (IIIe siècle av. J.-C.) prouve le lemme fondamental de la divisibilité : si un nombre premier divise un produit \(ab\), il divise \(a\) ou \(b\). Al-Karaji (Xe siècle) et les mathématiciens islamiques développent la théorie des congruences.
Le théorème des restes chinois (Sunzi Suanjing, IVe siècle, Chine) — trouver un entier connaissant ses restes par plusieurs diviseurs premiers entre eux — est un cas particulier du théorème de Bézout. Il est aujourd’hui fondamental en cryptographie.
📜 Lire l’article — Euclide et Thābit ibn Qurra : le plus vieil algorithme →
Résoudre \(7x + 11y = 1\) par l’algorithme d’Euclide étendu. Puis en déduire toutes les solutions de \(7x + 11y = 58\).
Le plus grand commun diviseur de \(a\) et \(b\) (non tous les deux nuls) est le plus grand entier positif qui divise à la fois \(a\) et \(b\). On le note \(\pgcd(a, b)\) ou \(a \wedge b\).
Pour \(a, b \in \mathbb{Z}\) avec \(b \neq 0\) et \(a = bq + r\) la division euclidienne :
\(\pgcd(a, b) = \pgcd(b, r)\)
En appliquant cette relation de façon répétée jusqu’à obtenir un reste nul, on obtient le PGCD.
Notons \(d = \pgcd(a, b)\) et \(d' = \pgcd(b, r)\).
Puisque \(r = a - bq\) et que \(d \mid a\), \(d \mid b\), par combinaison linéaire \(d \mid r\). Donc \(d\) divise \(b\) et \(r\), d’où \(d \le d'\).
De même, \(a = bq + r\) et \(d' \mid b\), \(d' \mid r\) impliquent \(d' \mid a\). Donc \(d' \le d\).
Finalement \(d = d'\). ∎
Pour calculer \(\pgcd(a, b)\) avec \(a > b > 0\) :
| Dividende | Diviseur | Quotient | Reste |
|---|---|---|---|
| 252 | 168 | 1 | 84 |
| 168 | 84 | 2 | 0 |
Dernier reste non nul : \(\pgcd(252, 168) = 84\).
| Dividende | Diviseur | Quotient | Reste |
|---|---|---|---|
| 1071 | 462 | 2 | 147 |
| 462 | 147 | 3 | 21 |
| 147 | 21 | 7 | 0 |
\(\pgcd(1071, 462) = 21\).
Deux entiers \(a\) et \(b\) sont premiers entre eux (ou copremiers) si \(\pgcd(a, b) = 1\).
Le PPCM (plus petit commun multiple) de \(a\) et \(b\) vérifie :
\(\text{ppcm}(a,b) = \dfrac{|a \cdot b|}{\pgcd(a,b)}\)
Pour tous entiers \(a, b\) non tous nuls, il existe des entiers \(u, v \in \mathbb{Z}\) tels que :
\(au + bv = \pgcd(a, b)\)
En particulier, \(a\) et \(b\) sont premiers entre eux si et seulement s’il existe \(u, v \in \mathbb{Z}\) tels que \(au + bv = 1\).
Considérons l’ensemble \(E = \{am + bn \mid m, n \in \mathbb{Z}\} \cap \mathbb{N}^*\), c’est-à-dire l’ensemble des combinaisons linéaires strictement positives de \(a\) et \(b\).
Étape 1 — \(E\) est non vide. Par exemple \(|a| = a \cdot (\pm 1) + b \cdot 0 \in E\) (en choisissant le signe).
Étape 2 — Soit \(d\) le plus petit élément de \(E\). Il existe (toute partie non vide de \(\mathbb{N}^*\) admet un minimum). Par définition, il existe \(u, v \in \mathbb{Z}\) tels que \(d = au + bv\).
Étape 3 — Montrons que \(d \mid a\). La division euclidienne donne \(a = dq + r\) avec \(0 \leqslant r < d\). Alors :
\(r = a - dq = a - (au + bv)q = a(1 - uq) + b(-vq)\)
Donc \(r\) est une combinaison linéaire de \(a\) et \(b\). Si \(r > 0\), alors \(r \in E\), ce qui contredit la minimalité de \(d\). Donc \(r = 0\) et \(d \mid a\). De même, \(d \mid b\).
Étape 4 — Montrons que \(d = \pgcd(a, b)\). On vient de voir que \(d\) est un diviseur commun. Soit \(c\) un autre diviseur commun de \(a\) et \(b\). Alors \(c \mid au + bv = d\). Donc tout diviseur commun divise \(d\), ce qui signifie que \(d\) est le plus grand diviseur commun. ∎
Les entiers \(u\) et \(v\) s’appellent les coefficients de Bézout. Ils ne sont pas uniques : si \((u_0, v_0)\) est une solution, alors toutes les solutions sont :
\(u = u_0 + \dfrac{b}{d}\,k, \quad v = v_0 - \dfrac{a}{d}\,k, \quad k \in \mathbb{Z}\)
où \(d = \pgcd(a,b)\).
Pour trouver les coefficients de Bézout de \(a\) et \(b\), on remonte les étapes de l’algorithme d’Euclide.
À chaque étape \(r_{k-1} = r_k q_{k+1} + r_{k+1}\), on a \(r_{k+1} = r_{k-1} - q_{k+1}\,r_k\).
On exprime chaque reste comme combinaison linéaire de \(a\) et \(b\).
Descente (algorithme d’Euclide) :
\(480 = 2\times 204 + 72\) ①
\(204 = 2\times 72 + 60\) ②
\(72 = 1\times 60 + 12\) ③ ← PGCD = 12 (dernier reste non nul)
\(60 = 5\times 12 + 0\)
Remontée (on isole \(12\) puis on substitue de bas en haut) :
D’après ③ : \(\quad 12 = 72 - 1\times 60\)
D’après ② : \(\quad 60 = 204 - 2\times 72\), donc
\(12 = 72 - 1\times(204 - 2\times 72) = 3\times 72 - 1\times 204\)
D’après ① : \(\quad 72 = 480 - 2\times 204\), donc
\(12 = 3\times(480 - 2\times 204) - 1\times 204 = 3\times 480 - 7\times 204\)
Coefficients de Bézout : \(u = 3\), \(v = -7\). Vérif : \(3\times 480 + (-7)\times 204 = 1\,440 - 1\,428 = 12\). ✓
Descente :
\(1071 = 2\times462 + 147\) ①
\(462 = 3\times147 + 21\) ②
\(147 = 7\times21 + 0\)
Remontée :
De ② : \(21 = 462 - 3\times147\)
De ① : \(147 = 1071 - 2\times462\)
Donc : \(21 = 462 - 3\times(1071 - 2\times462) = 7\times462 - 3\times1071\)
Coefficients : \(u = -3\), \(v = 7\). Vérif : \(-3\times1071 + 7\times462 = -3213+3234 = 21\). ✓
Si \(a \mid bc\) et \(\pgcd(a, b) = 1\), alors \(a \mid c\).
Puisque \(\pgcd(a,b)=1\), par Bézout il existe \(u, v \in \mathbb{Z}\) tels que \(au + bv = 1\).
En multipliant par \(c\) : \(auc + bvc = c\).
Or \(a \mid auc\) (évident) et \(a \mid bc\) donc \(a \mid bvc\).
Par combinaison linéaire : \(a \mid (auc + bvc) = c\). ∎
Si \(ac \equiv bc \pmod{n}\) et \(\pgcd(c, n) = 1\), alors \(a \equiv b \pmod{n}\).
\(ac \equiv bc \pmod{n}\) signifie \(n \mid (a-b)c\). Comme \(\pgcd(c,n)=1\), par Gauss \(n \mid (a-b)\), soit \(a \equiv b \pmod{n}\). ∎
(Annoncée au §9.1.) Pour \(a, b \in \mathbb{N}^*\), notons \(d = \pgcd(a, b)\), \(a = d a'\), \(b = d b'\) avec \(\pgcd(a', b') = 1\). Posons \(m = ab/d = d a' b'\).
(i) \(m\) est un multiple commun. \(m = a \cdot b'\) (donc \(a \mid m\)) et \(m = a' \cdot b\) (donc \(b \mid m\)).
(ii) \(m\) est le plus petit multiple commun. Soit \(k\) un multiple commun de \(a\) et \(b\). On écrit \(k = a\alpha = b\beta\) (\(\alpha, \beta \in \mathbb{N}\)). Alors \(da'\alpha = db'\beta\), soit \(a'\alpha = b'\beta\). Donc \(b' \mid a'\alpha\). Comme \(\pgcd(a', b') = 1\), le lemme de Gauss donne \(b' \mid \alpha\), soit \(\alpha = b'\gamma\) (\(\gamma \in \mathbb{N}\)). Alors \(k = a\alpha = a b' \gamma = m\gamma\), donc \(m \mid k\).
Ainsi \(m = \ppcm(a, b)\), et \(\pgcd(a,b) \times \ppcm(a,b) = d \times m = d \times \dfrac{ab}{d} = ab\). ∎
L’équation \(ax + by = c\) (avec \(a, b, c \in \mathbb{Z}\)) admet des solutions entières si et seulement si \(\pgcd(a, b) \mid c\).
Si \((x_0, y_0)\) est une solution particulière, toutes les solutions sont :
\(x = x_0 + \dfrac{b}{d}\,k, \quad y = y_0 - \dfrac{a}{d}\,k, \quad k \in \mathbb{Z}\)
Posons \(d = \pgcd(a, b)\).
Condition nécessaire. Si \((x_0, y_0)\) est solution, alors \(c = ax_0 + by_0\). Or \(d \mid a\) et \(d \mid b\), donc \(d \mid ax_0 + by_0 = c\).
Condition suffisante. Supposons \(d \mid c\). Par Bézout, il existe \(u, v\) tels que \(au + bv = d\). En multipliant par \(c/d\) : \(a\underbrace{(u \cdot c/d)}_{x_0} + b\underbrace{(v \cdot c/d)}_{y_0} = c\). C’est une solution particulière.
Forme générale. Soit \((x, y)\) une autre solution. Alors \(ax + by = ax_0 + by_0 = c\), donc \(a(x - x_0) = -b(y - y_0)\).
Posons \(a = da'\), \(b = db'\) avec \(\pgcd(a', b') = 1\). On obtient \(a'(x - x_0) = -b'(y - y_0)\).
Donc \(b' \mid a'(x - x_0)\). Comme \(\pgcd(a', b') = 1\), le lemme de Gauss (section 9.3) donne \(b' \mid (x - x_0)\), soit \(x - x_0 = b'k = \dfrac{b}{d}\,k\) pour un certain \(k \in \mathbb{Z}\).
En substituant : \(y - y_0 = -\dfrac{a}{d}\,k\). Réciproquement, tout couple de cette forme est solution. ∎
\(\pgcd(21, 15) = 3\) et \(3 \mid 6\) : des solutions existent.
On cherche d’abord \(21u + 15v = 3\). Par Euclide étendu : \(21 = 1\times15 + 6\), \(15 = 2\times6+3\), \(6=2\times3\). Remontée : \(3=15-2\times6=15-2(21-15)=3\times15-2\times21\).
Donc \(21\times(-2)+15\times3=3\). En multipliant par 2 : \(21\times(-4)+15\times6=6\).
Solution particulière : \(x_0=-4\), \(y_0=6\). Solutions générales :
\(x = -4 + 5k, \quad y = 6 - 7k, \quad k \in \mathbb{Z}\)
L’entier \(a\) admet un inverse modulo \(n\) (i.e. \(ax \equiv 1 \pmod{n}\) a une solution) si et seulement si \(\pgcd(a, n) = 1\).
Dans ce cas, l’inverse est donné par le coefficient de Bézout \(u\) tel que \(au + nv = 1\) : on a \(a^{-1} \equiv u \pmod{n}\).
Sens direct (\(\Rightarrow\)). Si \(ax \equiv 1 \pmod{n}\), il existe \(k \in \mathbb{Z}\) tel que \(ax = 1 + kn\), soit \(ax - kn = 1\). C’est une combinaison linéaire de \(a\) et \(n\) qui vaut 1. Tout diviseur commun de \(a\) et \(n\) divise donc 1, ce qui impose \(\pgcd(a, n) = 1\).
Sens réciproque (\(\Leftarrow\)). Si \(\pgcd(a, n) = 1\), par Bézout il existe \(u, v \in \mathbb{Z}\) tels que \(au + nv = 1\). En réduisant modulo \(n\) : \(au \equiv 1 \pmod{n}\). Donc \(u\) est l’inverse de \(a\) modulo \(n\). ∎
\(\pgcd(17, 100) = 1\) (car 17 est premier et ne divise pas 100).
Euclide étendu : \(100 = 5\times17+15\), \(17=1\times15+2\), \(15=7\times2+1\).
Remontée : \(1=15-7\times2=15-7(17-15)=8\times15-7\times17=8(100-5\times17)-7\times17=8\times100-47\times17\).
Donc \(-47\times17\equiv1\pmod{100}\), soit \(17^{-1}\equiv-47\equiv53\pmod{100}\).
Vérif : \(17\times53=901=9\times100+1\equiv1\pmod{100}\). ✓
Si \(\pgcd(a, b) = 1\) et \(a \mid n\) et \(b \mid n\), alors \(ab \mid n\).
Remarque historique : l'appellation usuelle « théorème de Gauss » désigne le lemme du §9.3. Le résultat ci-dessus en est une conséquence directe.
\(a \mid n\) donc \(n = ak\). Or \(b \mid n = ak\) et \(\pgcd(a,b)=1\), donc par Gauss \(b \mid k\). Ainsi \(k = bm\) et \(n = abm\), d’où \(ab \mid n\). ∎
Si \(4 \mid n\) et \(9 \mid n\), alors comme \(\pgcd(4,9)=1\), on a \(36 \mid n\).
Attention : si \(6 \mid n\) et \(4 \mid n\), on ne peut pas conclure \(24 \mid n\) car \(\pgcd(6,4)=2\neq1\). Contre-exemple : \(n=12\).
L’équation \(ax \equiv b \pmod{n}\) admet des solutions si et seulement si \(\pgcd(a, n) \mid b\).
Si \(d = \pgcd(a, n)\) divise \(b\), il y a exactement \(d\) classes de solutions modulo \(n\), toutes de la forme :
\(x \equiv x_0 + k\cdot\dfrac{n}{d} \pmod{n}, \quad k = 0, 1, \ldots, d-1\)
où \(x_0\) est une solution particulière.
Condition nécessaire. Si \(x\) est solution, alors \(n \mid ax - b\). Comme \(d = \pgcd(a,n) \mid a\), on a \(d \mid ax\). Et \(d \mid n \mid ax - b\), donc \(d \mid (ax) - (ax - b) = b\).
Condition suffisante et nombre de solutions. Posons \(d = \pgcd(a, n)\), \(a = da'\), \(n = dn'\) avec \(\pgcd(a', n') = 1\). Si \(d \mid b\), posons \(b = db'\).
L’équation \(ax \equiv b \pmod{n}\) devient \(da'x \equiv db' \pmod{dn'}\), soit \(a'x \equiv b' \pmod{n'}\). Comme \(\pgcd(a', n') = 1\), \(a'\) est inversible modulo \(n'\) (théorème de l’inverse modulaire ci-dessus) et l’on obtient l’unique solution \(x_0 \equiv b' (a')^{-1} \pmod{n'}\).
Les solutions modulo \(n = dn'\) sont les entiers \(x\) tels que \(x \equiv x_0 \pmod{n'}\), c’est-à-dire \(x = x_0 + n'k\) pour \(k \in \mathbb{Z}\). Parmi \(\{0, 1, \ldots, n-1\}\), il y a exactement \(d\) telles valeurs : \(x_0,\, x_0+n',\, x_0+2n',\, \ldots,\, x_0+(d-1)n'\). ∎
L’équation \(6x \equiv 5 \pmod{9}\) : \(\pgcd(6, 9) = 3\) et \(3 \nmid 5\). Pas de solution.
Si \(\pgcd(m, n) = 1\), le système \(\begin{cases}x \equiv a \pmod{m} \\ x \equiv b \pmod{n}\end{cases}\) admet une unique solution modulo \(mn\).
Existence. La première équation donne \(x = a + mk\) pour un certain \(k \in \mathbb{Z}\). En substituant dans la seconde : \(a + mk \equiv b \pmod{n}\), soit \(mk \equiv b - a \pmod{n}\). Comme \(\pgcd(m, n) = 1\), \(m\) est inversible modulo \(n\) (théorème de l’inverse modulaire ci-dessus) et l’on obtient \(k \equiv (b-a)m^{-1} \pmod{n}\). On en déduit une valeur de \(k\), puis une valeur de \(x = a + mk\).
Unicité modulo \(mn\). Si \(x\) et \(x'\) sont deux solutions, alors \(m \mid x - x'\) et \(n \mid x - x'\). Comme \(\pgcd(m,n) = 1\), le théorème de Gauss donne \(mn \mid x - x'\), c’est-à-dire \(x \equiv x' \pmod{mn}\). ∎
Résoudre \(\begin{cases}x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5}\end{cases}\).
De la 1ère : \(x = 3k + 2\). Substituer dans la 2e : \(3k + 2 \equiv 3 \pmod{5}\), soit \(3k \equiv 1 \pmod{5}\). Inverse de 3 mod 5 : \(3\times2=6\equiv1\), donc \(k \equiv 2 \pmod{5}\), soit \(k = 5j+2\).
Donc \(x = 3(5j+2)+2 = 15j+8\), soit \(x \equiv 8 \pmod{15}\).
Vérification : \(8 = 2\times3+2\) ✓, \(8 = 1\times5+3\) ✓.
Le petit théorème de Fermat (\(a^{p-1}\equiv 1 \pmod p\) pour \(p\) premier ne divisant pas \(a\)) est une application classique du lemme de Gauss et de l'inverse modulaire. Sa démonstration et ses applications sont étudiées au chapitre 10, section 10.5 (chapitre des nombres premiers, où il prend tout son sens).
Écrire une fonction euclide_etendu(a, b) qui implémente l’algorithme d’Euclide étendu de façon récursive.
(d, u, v) tel que \(au + bv = d = \pgcd(a, b)\).bezout(a, b) qui appelle la précédente et affiche le PGCD, les coefficients de Bézout et la vérification.Rappel Python : cas de base : si b == 0, retourner (a, 1, 0). Sinon, appel récursif sur (b, a % b). Division entière : a // b.
Écrire une fonction diophante(a, b, c) qui résout l’équation \(ax + by = c\) dans \(\mathbb{Z}\).
Rappel Python : math.gcd(a, b) pour le PGCD. Si \(au_0 + bv_0 = d\) alors \(x_0 = u_0 \cdot (c/d)\).
Explorer les inverses modulaires et vérifier le lemme de Gauss.
inverse_mod(a, n) qui retourne \(a^{-1} \bmod n\) si \(\pgcd(a,n)=1\), sinon None.Rappel Python : pow(a, -1, n) calcule l’inverse modulaire (Python 3.8+). math.gcd(a, n) pour le PGCD.
Programmer la résolution d’équations de congruence et le théorème chinois des restes :
resoudre_congruence(a, b, n) : résout \(ax \equiv b \pmod{n}\). L’équation a des solutions si et seulement si \(\text{pgcd}(a,n) \mid b\), et il y a alors \(d = \text{pgcd}(a,n)\) solutions modulo \(n\)crt(a, m, b, n) : applique le théorème chinois des restes pour résoudre le système \(\begin{cases} x \equiv a \pmod{m} \\ x \equiv b \pmod{n} \end{cases}\) avec \(\text{pgcd}(m,n) = 1\)Rappel Python : pow(a, -1, n) calcule l’inverse de \(a\) modulo \(n\) (Python 3.8+). math.gcd(a, n) donne le PGCD.
Observe comment on calcule les coefficients de Bezout pour 1071 et 462 : trouver u, v tels que 1071u + 462v = pgcd.
| Notion | Définition / Formule | Piège à éviter |
|---|---|---|
| Théorème de Bézout | \(\text{pgcd}(a,b) = 1 \iff \exists\, u, v \in \mathbb{Z},\; au + bv = 1\) | L’existence de \(u, v\) avec \(au + bv = 1\) est équivalente à la coprimalité, pas seulement une implication |
| Lemme de Gauss | Si \(a \mid bc\) et \(\text{pgcd}(a, b) = 1\) alors \(a \mid c\) | L’hypothèse \(\text{pgcd}(a, b) = 1\) est indispensable |
| Équation diophantienne | \(ax + by = c\) a des solutions ssi \(\text{pgcd}(a, b) \mid c\) | Si une solution existe, il y en a une infinité (famille affine) |
| Relation PGCD-PPCM | \(\text{pgcd}(a,b) \times \text{ppcm}(a,b) = |ab|\) | Valable uniquement pour deux entiers (pas pour trois ou plus directement) |
Euclide : \(11 = 7\times1+4\) ; \(7 = 4\times1+3\) ; \(4 = 3\times1+1\). Remontée : \(1 = 4-3 = 4-(7-4) = 2\times4-7 = 2(11-7)-7 = 2\times11-3\times7\). Donc \(7\times(-3)+11\times2=1\). Pour \(7x+11y=58\) : solution particulière \((x_0, y_0) = (-174, 116)\). Solution générale : \(x = -174+11k\), \(y = 116-7k\), \(k\in\mathbb{Z}\).
Bézout et Gauss : teste d’abord ton intuition.
« Si \(\pgcd(a,b)=1\) alors \(a\) et \(b\) sont des nombres premiers. »
Cette affirmation est-elle vraie ?
C’est faux ! « Premiers entre eux » signifie que leur pgcd vaut 1, ce qui n’a rien à voir avec être un nombre premier. Par exemple : \(\pgcd(8,15)=1\), mais 8 et 15 ne sont pas premiers (\(8=2^3\), \(15=3\times 5\)).
Mini-test : 9 et 25 sont :
Voir section 2
« L’équation \(au + bv = \pgcd(a,b)\) a une unique solution \((u,v)\). »
Cette affirmation est-elle vraie ?
C’est faux ! Le théorème de Bézout garantit l'existence de solutions, mais il y en a une infinité. Si \((u_0, v_0)\) est solution, alors \((u_0 + k\frac{b}{d}, v_0 - k\frac{a}{d})\) est aussi solution pour tout \(k \in \mathbb{Z}\), avec \(d = \pgcd(a,b)\).
Mini-test : \(3u + 5v = 1\). Si \((u,v)=(2,-1)\) est solution, \((7,-4)\) l’est-elle aussi ?
Voir section 2
« Si \(a\) divise \(bc\), alors \(a\) divise \(b\) ou \(a\) divise \(c\). »
Cette affirmation est-elle vraie ?
C’est faux en général ! Par exemple : \(6 \mid 12 = 4 \times 3\), mais \(6 \nmid 4\) et \(6 \nmid 3\). Cette propriété n’est vraie que si \(a\) est premier (lemme d’Euclide) ou si \(\pgcd(a,b)=1\) (lemme de Gauss).
Mini-test : \(12 \mid 36\). Sait-on que \(12 \mid 9\) ou \(12 \mid 4\) ?
Voir section 3
« L’équation \(ax \equiv b \pmod{n}\) admet toujours une solution. »
Cette affirmation est-elle vraie ?
C’est faux ! L’équation \(ax \equiv b \pmod{n}\) admet une solution si et seulement si \(\pgcd(a,n) \mid b\). Par exemple : \(2x \equiv 3 \pmod{4}\) n’a pas de solution car \(\pgcd(2,4)=2\) et \(2 \nmid 3\).
Mini-test : \(3x \equiv 5 \pmod{7}\). Cette équation a-t-elle une solution ?
Voir section 5
« S’il existe \(u, v \in \mathbb{Z}\) tels que \(au + bv = d\), alors \(d = \pgcd(a,b)\). »
Cette affirmation est-elle vraie ?
C’est faux ! La réciproque de Bézout n’est pas vraie dans ce sens. On sait seulement que \(\pgcd(a,b)\) divise \(d\). Par exemple : \(3 \times 1 + 5 \times 1 = 8\), mais \(\pgcd(3,5) = 1 \neq 8\). Le théorème de Bézout dit que \(\pgcd(a,b)\) est le plus petit entier positif de la forme \(au+bv\).
Mini-test : \(4 \times 2 + 6 \times (-1) = 2\). Alors \(\pgcd(4,6) =\) :
Voir section 2
« Si \(\pgcd(a,b)=1\) et \(\pgcd(a,c)=1\), alors \(\pgcd(a,bc)=1\). »
Cette affirmation est-elle vraie ?
C’est vrai ! C’est une conséquence directe du théorème de Gauss. Par Bézout : \(au+bv=1\) et \(au'+cv'=1\). En multipliant : \((au+bv)(au'+cv') = 1\), ce qui donne \(a(\ldots) + bc(vv') = 1\), donc par Bézout \(\pgcd(a,bc)=1\).
Mini-test : \(\pgcd(5,6)=1\) et \(\pgcd(5,7)=1\). Alors \(\pgcd(5,42)\) vaut :
Voir section 3