PGCD, Bézout et nombres premiers en maths sup (MPSI) : cours et méthodes

L’entier \(b\) est un diviseur de \(a\), ce qu’on écrit \(b \mid a\), lorsque \(a = kb\) pour un certain \(k \in \mathbb{Z}\). Dans ce cas, \(a\) est aussi appelé multiple de \(b\) ; les multiples de \(b\) forment l’ensemble \(b\mathbb{Z}\).

Pour \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^*\), on peut trouver un et un seul couple d’entiers \((q, r)\) vérifiant

\[a = qb + r,\qquad r \in \{0, 1, \ldots, b – 1\}.\]

On appelle \(q\) le quotient et \(r\) le reste de la division.

Existence : on pose \(q = \lfloor a/b \rfloor\). Par définition de la partie entière, \(q \leqslant a/b < q + 1\). On multiplie par \(b > 0\), puis on retranche \(bq\) : on obtient \(0 \leqslant a – bq < b\). Ainsi, \(r = a – bq\) convient.

Unicité : si \(bq + r = bq^{\prime} + r^{\prime}\) avec les deux restes dans \([0, b[\), alors \(b\,|q – q^{\prime}| = |r^{\prime} – r| < b\). Par conséquent, \(|q – q^{\prime}| < 1\), donc \(q = q^{\prime}\), puis \(r = r^{\prime}\).

Montrons qu’aucun entier de la forme \(8k + 7\) n’est somme de trois carrés. D’abord, le carré d’un entier pair \(2m\) vaut \(4m^2\), dont le reste modulo \(8\) est \(0\) ou \(4\). Ensuite, le carré d’un entier impair \(2m + 1\) vaut \(4m(m + 1) + 1\). Or \(m(m + 1)\) est pair, donc ce carré a pour reste \(1\) modulo \(8\).

Ainsi, un carré a pour reste \(0\), \(1\) ou \(4\) modulo \(8\). On examine ensuite toutes les sommes de trois tels restes : on obtient \(0\), \(1\), \(2\), \(3\), \(4\), \(5\) ou \(6\) modulo \(8\), jamais \(7\). La conclusion suit.

Le PGCD de \(a\) et \(b\), noté \(a \wedge b\), est le plus grand diviseur positif commun à \(a\) et \(b\). Par convention, \(0 \wedge 0 = 0\). Les entiers \(a\) et \(b\) sont dits premiers entre eux si \(a \wedge b = 1\).

Supposons \(a = bq + r\), où \(q\) est un entier. Les couples \((a, b)\) et \((b, r)\) possèdent alors exactement les mêmes diviseurs communs ; par suite, \(a \wedge b = b \wedge r\).

Un diviseur commun de \(a\) et \(b\) divise \(r = a – bq\). Inversement, un diviseur commun de \(b\) et \(r\) divise \(a = bq + r\). Les deux ensembles de diviseurs communs sont donc égaux, et ils ont le même plus grand élément.

Calculons \(5313 \wedge 2093\). On écrit les divisions successives :

\[5313 = 2 \times 2093 + 1127,\quad 2093 = 1 \times 1127 + 966,\quad 1127 = 1 \times 966 + 161,\quad 966 = 6 \times 161 + 0.\]

Le dernier reste non nul est \(161\). Donc \(5313 \wedge 2093 = 161\). On vérifie d’ailleurs que \(5313 = 161 \times 33\) et \(2093 = 161 \times 13\).

Pour \(a\) et \(b\) non nuls, le PPCM de \(a\) et \(b\), noté \(a \vee b\), est le plus petit multiple strictement positif commun à \(a\) et \(b\). Plus généralement, le PGCD d’une famille \((a_1, \ldots, a_n)\) non toute nulle est le plus grand diviseur positif commun à tous les \(a_i\).

Relation de Bézout. Pour tous \(a, b \in \mathbb{Z}\), il existe \(u, v \in \mathbb{Z}\) tels que \(au + bv = a \wedge b\).

Théorème de Bézout. On a \(a \wedge b = 1\) exactement lorsque l’équation \(au + bv = 1\) possède au moins une solution \((u, v) \in \mathbb{Z}^2\).

La relation découle de l’algorithme étendu décrit ci-dessous. Pour le théorème, le sens direct est un cas particulier de la relation. Réciproquement, si \(au + bv = 1\), tout diviseur commun positif de \(a\) et \(b\) divise \(1\). Il vaut donc \(1\), d’où \(a \wedge b = 1\).

Soit \(d\) le PGCD d’une famille finie \((a_1, \ldots, a_n)\). On peut alors choisir des entiers \(u_i\) de sorte que \(\sum_{i=1}^{n} u_ia_i = d\).

Pour obtenir des coefficients de Bézout de \(a\) et \(b\) :

1. écrire toutes les divisions de l’algorithme d’Euclide, en isolant chaque reste : \(r = x – qy\) ;
2. partir de la dernière égalité, qui exprime le PGCD à l’aide des deux restes précédents ;
3. remplacer à chaque étape le plus petit reste par son expression, en regroupant les termes ;
4. s’arrêter lorsque seuls \(a\) et \(b\) apparaissent, puis vérifier le résultat numériquement.

Cherchons une relation de Bézout entre \(61\) et \(22\). Les divisions sont \(61 = 2 \times 22 + 17\), \(22 = 1 \times 17 + 5\), \(17 = 3 \times 5 + 2\) et \(5 = 2 \times 2 + 1\). On remonte ensuite :

\[1 = 5 – 2 \times 2 = 5 – 2(17 – 3 \times 5) = 7 \times 5 – 2 \times 17.\]

Puis on remplace \(5 = 22 – 17\), ce qui donne \(1 = 7 \times 22 – 9 \times 17\). Enfin, avec \(17 = 61 – 2 \times 22\), on obtient

\[1 = 25 \times 22 – 9 \times 61.\]

On vérifie : \(25 \times 22 = 550\) et \(9 \times 61 = 549\). Ainsi, \(u = -9\) et \(v = 25\) conviennent pour \(61u + 22v = 1\).

Pour éviter la remontée, on peut calculer les coefficients en même temps que les restes. On tient un tableau dont chaque ligne contient un reste \(r_k\) et deux entiers \(u_k\), \(v_k\) tels que \(r_k = au_k + bv_k\). On part des lignes \((a, 1, 0)\) et \((b, 0, 1)\). Ensuite, chaque nouvelle ligne s’obtient en retranchant \(q\) fois la ligne précédente à l’avant-dernière, où \(q\) est le quotient de la division en cours. La ligne du PGCD donne directement les coefficients.

Lemme de Gauss. Si \(a \mid bc\) et \(a \wedge b = 1\), alors \(a \mid c\).

Par le théorème de Bézout, il existe \(u\) et \(v\) tels que \(au + bv = 1\). On multiplie par \(c\) : \(c = acu + bcv\). Or \(a\) divise \(acu\), et \(a\) divise \(bc\) par hypothèse. Par conséquent, \(a\) divise la somme, c’est-à-dire \(c\).

Si \(a \mid c\), \(b \mid c\) et \(a \wedge b = 1\), alors \(ab \mid c\). De plus, pour \(a\) et \(b\) non nuls, on a \((a \wedge b)(a \vee b) = |ab|\).

L’hypothèse \(a \wedge b = 1\) est indispensable. Par exemple, \(6\) divise \(4 \times 9 = 36\), mais \(6\) ne divise ni \(4\) ni \(9\). En effet, \(6 \wedge 4 = 2 \neq 1\).

1. Calculer \(d = a \wedge b\). Si \(d\) ne divise pas \(c\), il n’y a aucune solution.
2. Sinon, diviser par \(d\) : on obtient \(\alpha x + \beta y = \gamma \) avec \(\alpha \wedge \beta = 1\).
3. Trouver une solution particulière \((x_0, y_0)\), à vue ou par l’algorithme étendu.
4. Soustraire : \(\alpha (x – x_0) = -\beta (y – y_0)\). Le lemme de Gauss donne \(\beta \mid x – x_0\), donc \(x = x_0 + k\beta \), puis \(y = y_0 – k\alpha \).
5. Vérifier la réciproque : ces couples sont bien solutions pour tout \(k \in \mathbb{Z}\).

Résolvons \(21x + 15y = 9\). D’abord, \(21 \wedge 15 = 3\), qui divise \(9\). On simplifie : \(7x + 5y = 3\). Ensuite, on remarque que \(7 \times (-1) + 5 \times 2 = 3\). Par soustraction, \(7(x + 1) = -5(y – 2)\).

Ainsi, \(5\) divise \(7(x + 1)\) et \(5 \wedge 7 = 1\). Par le lemme de Gauss, \(5 \mid x + 1\) : il existe \(k \in \mathbb{Z}\) tel que \(x = -1 + 5k\). On en déduit \(y = 2 – 7k\). Réciproquement, \(7(-1 + 5k) + 5(2 – 7k) = 3\) pour tout \(k\). Les solutions sont donc les couples \((-1 + 5k,\; 2 – 7k)\), \(k \in \mathbb{Z}\).

Un nombre premier est un entier \(p \geqslant 2\) qui n’admet que deux diviseurs positifs : \(1\) et lui-même. L’ensemble de ces entiers est désigné par \(\mathcal{P}\).

L’ensemble \(\mathcal{P}\) des nombres premiers est infini.

Supposons \(\mathcal{P}\) fini, égal à \(\{p_1, \ldots, p_r\}\). On pose \(N = p_1 p_2 \cdots p_r + 1 \geqslant 2\). L’entier \(N\) admet un diviseur premier \(p_i\). Or \(p_i\) divise aussi le produit \(p_1 \cdots p_r\), donc il divise la différence, qui vaut \(1\). C’est absurde.

Tout entier \(n \geqslant 2\) s’écrit de manière unique, à l’ordre près, comme produit de nombres premiers :

\[n = \prod_{p \in \mathcal{P}} p^{v_p(n)},\]

où les exposants \(v_p(n) \in \mathbb{N}\) sont nuls sauf un nombre fini. L’entier \(v_p(n)\) est la valuation p-adique de \(n\).

Pour tous entiers \(a, b \geqslant 1\) et tout premier \(p\) :

• \(v_p(ab) = v_p(a) + v_p(b)\) ;
• \(a \mid b\) si et seulement si \(v_p(a) \leqslant v_p(b)\) pour tout premier \(p\) ;
• la valuation de \(a \wedge b\) en \(p\) est la plus petite des deux valeurs \(v_p(a)\), \(v_p(b)\), et celle de \(a \vee b\) est la plus grande.

Prenons \(a = 1188 = 2^2 \times 3^3 \times 11\) et \(b = 2520 = 2^3 \times 3^2 \times 5 \times 7\). On compare les exposants premier par premier. Le PGCD prend les minimums : \(2^2 \times 3^2 = 36\). Le PPCM prend les maximums : \(2^3 \times 3^3 \times 5 \times 7 \times 11 = 83160\). On contrôle enfin : \(36 \times 83160 = 2993760 = 1188 \times 2520\).

Pour tout premier \(p\) et tout \(n \in \mathbb{N}^*\) :

\[v_p(n!) = \sum_{j \geqslant 1}\left\lfloor \frac{n}{p^j} \right\rfloor,\]

la somme étant finie, car ses termes sont nuls dès que \(p^j > n\).

Soit \(n \in \mathbb{N}^*\). Deux entiers \(a\) et \(b\) sont congrus modulo \(n\) si \(n \mid a – b\). On écrit alors \(a \equiv b\;[n]\). De façon équivalente, les divisions euclidiennes de \(a\) et de \(b\) par \(n\) fournissent le même reste.

Il existe un entier \(u\) tel que \(au \equiv 1\;[n]\) si et seulement si \(a \wedge n = 1\). Un tel \(u\) est un inverse de \(a\) modulo \(n\) ; il est unique modulo \(n\).

L’égalité \(au \equiv 1\;[n]\) signifie qu’il existe \(v\) tel que \(au + nv = 1\). Le théorème de Bézout donne donc l’équivalence. Pour l’unicité, si \(au \equiv au^{\prime} \equiv 1\;[n]\), on multiplie par \(u\) : \(u \equiv u(au^{\prime}) = (ua)u^{\prime} \equiv u^{\prime}\;[n]\).

Soit \(p\) un nombre premier. Pour tout \(a \in \mathbb{Z}\), \(a^p \equiv a\;[p]\). Si de plus \(p\) ne divise pas \(a\), alors \(a^{p – 1} \equiv 1\;[p]\).

D’abord, pour \(1 \leqslant k \leqslant p – 1\), la formule du pion donne \(\binom{p}{k} = \frac{p}{k}\binom{p – 1}{k – 1}\). Après multiplication par \(k\), on voit que \(p\) divise \(k\binom{p}{k}\) et \(p \wedge k = 1\), donc \(p\) divise \(\binom{p}{k}\) par le lemme de Gauss. La formule du binôme donne alors \((a + 1)^p \equiv a^p + 1\;[p]\).

Ensuite, une récurrence sur \(a \in \mathbb{N}\) donne \(a^p \equiv a\;[p]\). Pour \(a\) négatif, on remplace \(a\) par son reste modulo \(p\). Enfin, si \(p \nmid a\), alors \(p\) divise \(a(a^{p – 1} – 1)\) et \(p \wedge a = 1\) : le lemme de Gauss donne \(a^{p – 1} \equiv 1\;[p]\).

Calculons le reste de \(3^{2026}\) modulo \(11\). Le nombre \(11\) est premier et ne divise pas \(3\), donc \(3^{10} \equiv 1\;[11]\). Or \(2026 = 10 \times 202 + 6\), d’où \(3^{2026} \equiv 3^6\;[11]\).

Enfin, \(3^6 = 729 = 66 \times 11 + 3\). Le reste cherché vaut donc \(3\). On aurait aussi pu remarquer que \(3^5 = 243 \equiv 1\;[11]\), ce qui raccourcit encore le calcul.

• S’exercer : exercices corrigés de maths sup (MPSI) sur PGCD, Bézout et nombres premiers
• Bases utiles : Quantificateurs, raisonnements et rédaction
• Chapitre d’avant : Fonctions convexes et inégalités de convexité
• Chapitre d’après : Lois internes, groupes, anneaux et corps
• Vérifier ses acquis : QCM de maths sup (MPSI) sur PGCD, Bézout et nombres premiers
• Contrôle corrigé en temps limité : Équations diophantiennes et valuations : contrôle de maths en MPSI
• Tous les chapitres : le sommaire de maths sup (MPSI)
• Après le bac : les maths post-bac, de la MPSI à la L3