Théorème de Gauss en arithmétique : de « a divise bc » aux équations ax + by = c

Le théorème de Gauss fait partie de l'arithmétique de l'option maths expertes de terminale. Le programme de 2019 le place juste après le théorème de Bézout et range sa démonstration parmi celles qu'il faut savoir refaire.

L'énoncé, et pourquoi l'hypothèse ne se discute pas

Soient a, b, c des entiers relatifs avec a ≠ 0. Si a divise bc et si PGCD(a ; b) = 1, alors a divise c.

Sans l'hypothèse « premiers entre eux », la conclusion tombe : 6 divise 4 × 3 = 12, mais 6 ne divise ni 4 ni 3. Ici PGCD(6 ; 4) = 2, et une partie du 6 se loge dans le 4, l'autre dans le 3. Quand a et b n'ont aucun facteur commun, ce partage est impossible.

Lorsque a est un nombre premier p, PGCD(p ; b) = 1 dès que p ne divise pas b. On obtient le lemme d'Euclide : si p premier divise bc, alors p divise b ou p divise c. Il sert à l'unicité de la décomposition, traitée dans l'article sur les nombres premiers et la décomposition.

La démonstration par Bézout, et le corollaire

Théorème. Comme PGCD(a ; b) = 1, le théorème de Bézout donne deux entiers u et v tels que au + bv = 1. On multiplie par c : c = acu + bcv. Le nombre a divise acu, et il divise bc par hypothèse, donc bcv. Il divise la somme : a divise c.

Corollaire. Si a et b sont premiers entre eux et divisent tous deux n, alors ab divise n. En effet, a divise n, donc n = ak avec k entier. Alors b divise ak et PGCD(b ; a) = 1 : par le théorème de Gauss, b divise k, soit k = bk′. Donc n = abk′.

Le corollaire remplace deux divisibilités par une seule : un entier divisible par 4 et par 9 est divisible par 36. Il ne vaut plus sans l'hypothèse : 18 est divisible par 6 et par 9, mais pas par 54.

Résoudre ax + by = c en nombres entiers

La méthode attendue en devoir surveillé tient en cinq temps, et je fais justifier chacun sur la copie.

• Calculer d = PGCD(a ; b). Si d ne divise pas c, il n'y a aucune solution ; sinon on divise l'équation par d, et les nouveaux coefficients sont premiers entre eux.
• Trouver une solution particulière (x₀ ; y₀), à vue ou en multipliant par c un couple de Bézout.
• Soustraire les deux égalités : a(x − x₀) = b(y₀ − y).
• Appliquer Gauss : b divise a(x − x₀) et PGCD(a ; b) = 1, donc b divise x − x₀, soit x = x₀ + bk avec k ∈ ℤ. En reportant, abk = b(y₀ − y), donc y = y₀ − ak.
• Vérifier la réciproque : pour tout k ∈ ℤ, a(x₀ + bk) + b(y₀ − ak) = ax₀ + by₀ = c. Sans cette ligne, on a seulement montré que les solutions sont parmi ces couples.

Exemple 1 · 7x + 5y = 3

Solution particulière. PGCD(7 ; 5) = 1 et 7 × (−2) + 5 × 3 = 1. En multipliant par 3 : 7 × (−6) + 5 × 9 = 3. Le couple (−6 ; 9) est solution.

Toutes les solutions. Si 7x + 5y = 3, alors 7x + 5y = 7 × (−6) + 5 × 9, donc 7(x + 6) = 5(9 − y). Ainsi 5 divise 7(x + 6) ; comme PGCD(5 ; 7) = 1, le théorème de Gauss donne : 5 divise x + 6. Il existe k ∈ ℤ tel que x = −6 + 5k. En reportant, 7 × 5k = 5(9 − y), donc y = 9 − 7k.

Réciproque. Pour tout k ∈ ℤ, 7(−6 + 5k) + 5(9 − 7k) = −42 + 45 = 3. Les solutions sont les couples (−6 + 5k ; 9 − 7k), k ∈ ℤ, par exemple (−1 ; 2), (4 ; −5), (9 ; −12).

Exemple 2 · 6x + 15y = 9, où il faut d'abord simplifier

Rédaction. PGCD(6 ; 15) = 3, qui divise 9 : il y a des solutions, et l'équation équivaut à 2x + 5y = 3. Le couple (−1 ; 1) convient. Si 2x + 5y = 3, alors 2(x + 1) = 5(1 − y) ; 5 divise 2(x + 1) et PGCD(5 ; 2) = 1, donc x = −1 + 5k, puis y = 1 − 2k. Réciproquement, 2(−1 + 5k) + 5(1 − 2k) = 3. Les solutions sont (−1 + 5k ; 1 − 2k), k ∈ ℤ.

Sans la division par 3, on écrit 6(x + 1) = 15(1 − y), et Gauss ne s'applique pas directement à 15 et 6, qui ne sont pas premiers entre eux.

Exemple 3 · Les racines rationnelles de 2x³ + x² + x − 1

Le programme cite ce problème parmi les « problèmes possibles ». On cherche les rationnels r tels que P(r) = 0, où P(x) = 2x³ + x² + x − 1.

Rédaction. On écrit r = p/q sous forme irréductible, avec q ≥ 1 et PGCD(p ; q) = 1. En multipliant P(p/q) = 0 par q³ : 2p³ + p²q + pq² − q³ = 0.

D'une part, q³ = p(2p² + pq + q²), donc p divise q³. Comme p est premier avec q, il est premier avec q³ (exercice 3 de l'article sur Bézout), et p divise 1 × q³ avec PGCD(p ; q³) = 1 : par Gauss, p divise 1, donc p = ±1. D'autre part, 2p³ = q(q² − pq − p²), donc q divise 2p³ ; q est premier avec p³, donc q divise 2 : q = 1 ou q = 2.

Les seuls candidats sont 1, −1, 1/2 et −1/2. Or P(1) = 3, P(−1) = −3, P(−1/2) = −3/2 et P(1/2) = 2/8 + 1/4 + 1/2 − 1 = 0. La seule racine rationnelle est 1/2. On peut même conclure sur ℝ : P(x) = (2x − 1)(x² + x + 1), et x² + x + 1 a un discriminant égal à −3, négatif.

Les solutions de 7x + 5y = 3 sur la droite

La figure reprend l'exemple 1. La droite d'équation 7x + 5y = 3 se trace d'abord : elle contient une infinité de points, mais seuls ceux à coordonnées entières sont des solutions. Le point (−6 ; 9) apparaît ensuite, puis trois sauts du même vecteur de coordonnées (5 ; −7) mènent à (−1 ; 2), (4 ; −5) et (9 ; −12). Les formules x = −6 + 5k, y = 9 − 7k s'affichent pour finir. Le théorème de Gauss explique pourquoi aucun point entier de la droite n'échappe à ces sauts : entre deux solutions, l'écart des abscisses est forcément un multiple de 5.

Les erreurs sur le théorème de Gauss qui coûtent des points

• Appliquer Gauss sans écrire PGCD(a ; b) = 1 : sans elle, la conclusion peut être fausse.
• Se tromper de diviseur : dans 7(x + 6) = 5(9 − y), c'est 5 qui divise x + 6, pas 7.
• Oublier la réciproque, ou poser x = x₀ + bk et y = y₀ + ak avec le mauvais signe ; la réciproque l'aurait montré.
• Résoudre sans diviser par le PGCD quand les coefficients ne sont pas premiers entre eux.

Trois exercices corrigés sur le théorème de Gauss

Exercice 1 · Divisible par 6, sans calculer

Énoncé. a) Montrer qu'un entier divisible par 6 et par 9 n'est pas forcément divisible par 54. b) Montrer que, pour tout n ∈ ℕ, n(n + 1)(2n + 1) est divisible par 6.

Correction. a) 18 est divisible par 6 et par 9, mais pas par 54. Le corollaire ne s'applique pas, car PGCD(6 ; 9) = 3.

b) Parmi n et n + 1, l'un est pair : 2 divise le produit. Pour 3, on raisonne sur le reste de n modulo 3 : si n ≡ 0 [3], 3 divise n ; si n ≡ 2 [3], 3 divise n + 1 ; si n ≡ 1 [3], 2n + 1 ≡ 3 ≡ 0 [3]. Dans tous les cas, 3 divise le produit. Comme 2 et 3 sont premiers entre eux, le corollaire du théorème de Gauss donne : 6 divise n(n + 1)(2n + 1).

Exercice 2 · 13x − 8y = 3

Énoncé. Résoudre dans ℤ² l'équation 13x − 8y = 3.

Correction. 13 × 5 − 8 × 8 = 65 − 64 = 1, donc PGCD(13 ; 8) = 1. On repère aussi la solution (−1 ; −2) : 13 × (−1) − 8 × (−2) = −13 + 16 = 3.

Si 13x − 8y = 3, alors 13(x + 1) = 8(y + 2). 8 divise 13(x + 1) et PGCD(8 ; 13) = 1, donc 8 divise x + 1 : x = −1 + 8k, k ∈ ℤ. En reportant, 13 × 8k = 8(y + 2), donc y = −2 + 13k. Réciproquement, 13(−1 + 8k) − 8(−2 + 13k) = −13 + 16 = 3. Les solutions sont (−1 + 8k ; −2 + 13k), k ∈ ℤ.

Exercice 3 · 300 € en jetons de 17 € et de 11 €

Énoncé. Un jeu vend des jetons à 17 € et à 11 €. On dépense exactement 300 €. Combien de jetons de chaque sorte peut-on avoir achetés ?

Correction. On cherche les entiers naturels x, y tels que 17x + 11y = 300. On a 17 × 2 + 11 × (−3) = 1, donc 17 × 600 + 11 × (−900) = 300. Comme précédemment, 17(x − 600) = 11(−900 − y), 11 divise 17(x − 600) et PGCD(11 ; 17) = 1, donc x = 600 − 11k, puis y = −900 + 17k, avec k ∈ ℤ ; la réciproque se vérifie : 17(600 − 11k) + 11(−900 + 17k) = 300.

On impose x ≥ 0 et y ≥ 0 : k ≤ 600/11 ≈ 54,5 et k ≥ 900/17 ≈ 52,9, donc k = 53 ou k = 54. On obtient (17 ; 1) et (6 ; 18). Vérification : 17 × 17 + 11 × 1 = 300 et 17 × 6 + 11 × 18 = 102 + 198 = 300. On a donc acheté soit 17 jetons à 17 € et 1 à 11 €, soit 6 à 17 € et 18 à 11 €.