Le lemme de Gauss

Théorème d'arithmétique de Gauss

« La mathématique est la reine des sciences et l’arithmétique est la reine des mathématiques » (C. F. Gauss).

Carl Friedrich Gauß (en français, Gauss) reste l’un des mathématiciens les plus célèbres de tous les temps. Né en 1777 dans ce qui était alors la principauté de Brunswick-Wolfenbüttel (au nord de l’Allemagne d’aujourd’hui), il publia en 1801 son ouvrage Disquisitiones arithmeticae (une œuvre de jeunesse, donc). Ce livre de référence était, entre autres choses, un « état des lieux » de l’arithmétique de l’époque mais surtout, Gauss y apporta ses propres découvertes et des notions nouvelles (comme celle de congruence), jetant les bases de la théorie des nombres.

Note : le théorème d'arithmétique qui porte son nom figurait déjà dans les Éléments d'Euclide.

Ci-dessous, on considérera \(a,\) \(b\) et \(c\) trois entiers relatifs non nuls.

 

Théorème

Si \(a\) divise \(bc\) et si \(a\) et \(b\) sont premiers entre eux, alors \(a\) divise \(c.\)

Par exemple \(a = 3\) et il divise 30 (\(b = 2\) et \(c = 15),\) \(a\) et \(b\) étant bien premiers entre eux. Alors 15 divise 30.

On le démontre facilement car si \(a\) divise \(bc,\) il existe un entier relatif \(k\) tel que \(bc = ka.\) Comme \(a\) et \(b\) sont premiers entre eux, il existe un couple d’entiers relatifs \((u\,; v)\) tel que \(au + bv = 1\) (théorème de Bézout).

Multiplions les deux membres de l’égalité par \(c.\)

\(cau + cbv = c\)

Comme \(bc = ka,\) nous pouvons écrire \(cau + kav = c.\)

Factorisons. \(a(cu + kv) = c.\)

Comme \((cu + kv)\) est un entier relatif, \(a\) divise \(c.\)

 

Corollaires

On peut déduire du théorème certaines propriétés, au demeurant plutôt évidentes.

Si \(a\) et \(b\) d’une part, \(a\) et \(c\) d’autre part sont premiers entre eux, alors \(a\) et \(bc\) sont premiers entre eux.

Si \(a\) et \(b\) sont premiers entre eux et si \(a\) et \(b\) divisent \(c,\) alors \(ab\) divise \(c.\)

 

Exemple

Soit l’équation diophantienne \(42 x + 26y = 2.\) Elle est résolue en page de théorème de Bézout. Nous trouvons une solution particulière : \((5\,; -8).\) À présent, le théorème de Gauss va nous permettre de déterminer TOUTES les solutions.

À partir de l’équation de départ, nous allons soustraire l’équation avec solutions particulières.

\(42x + 26y - 42 × 5 - 26(-8)\) \(=\) \(3 - 3\)
\(⇔ 42(x - 5) + 26(y + 8) = 0\)
\(⇔ 21(x - 5) = -13(y + 8)\)

13 et 21 sont premiers entre eux. Donc, d’après le théorème de Gauss, 21 divise \(y + 8.\) D’où \(y + 8 = 21k,\) avec \(k\) entier relatif. Donc \(y = 21k - 8.\)

Cette première solution nous permet de revenir à notre équation.

\(21(x - 5)\) \(=\) \(-13(21k - 8 + 8)\)
\(⇔ 21x - 105 = -273k\)
\(⇔ 21x = -273k + 105\) (tout se divise par 21)
\(⇔ x = -13k + 5.\)

Les couples d’entiers relatifs qui sont solutions de l’équation s’écrivent donc sous la forme \((-13k + 5\,;21k - 8).\)

Vous avez deux minutes pour le vérifier avec un relatif \(k\) donné ? OK, allons-y. Prenons \(k = -2.\)

Dans ce cas \(x = 31\) et \(y = -50.\)
\(42 × 31 + 26 × (-50)\)
\(= 1302 - 1300 = 2\)

 

Exercices

Exercice 1

Soit l’équation (E) définie par : \(11x + 21y = 3,\) avec \(x\) et \(y\) entiers relatifs.

Démontrer que \(x\) est un multiple de 3 pour tout couple \((x\,; y)\) solution de (E).

Exercice 2

Soit l’équation (E) définie par : \(7x + 5y = 2,\) avec \(x\) et \(y\) entiers relatifs.

  1. Justifier que (E) admet pour solution au moins un couple \((x\,; y)\)
  2. Déterminer un couple d’entiers \((x_0\,;y_0)\) solution de (E).
  3. Montrer que (E) a les mêmes solutions que (E’) : \(7(x - x_0) = -5(y - y_0)\)
  4. Montrer que si le couple \((x\,; y)\) est solution de (E) alors il existe un entier \(k\) tel que \(x = 5k + 1\) et \(y = -7k - 1.\)
  5. Déterminer l’ensemble des couples d’entiers solutions de (E).

 

Corrigés

Corrigé 1

On déduit de (E) l’équivalence suivante : \(2x + 0y \equiv 0[3].\)

Donc \(2x \equiv 0[3].\)

Le produit \(2x\) est donc divisible par 3. Or, 2 et 3 sont premiers entre eux. Donc, d’après le théorème de Gauss, 3 divise \(x.\)

Par conséquent, \(x\) est un multiple de 3 pour tout couple de solutions entières.

Corrigé 2

1- Nous savons que 7 et 5 sont premiers entre eux. Donc, d’après le théorème de Bézout l’équation \(7x + 5y = 1\) admet un couple de solutions entières.

Donc \(7(2x) + 5(2y) = 2.\) Ainsi (E) admet au moins un couple de solutions.

2- On repère facilement que \((1\,; -1)\) est un couple solution.

3-  (E) : \(7x + 5y = 2\)

Or \(7x_0 + 5y_0 = 2\)

On remplace : \(7x + 5y = 7x_0 + 5y_0\)

\(⇔ 7(x - x_0)\) \(=\) \(-5(y - y_0)\)

4- Nous combinons les résultats des deux questions précédentes : \(7(x - 1)\) \(=\) \(-5(y - 1)\)

Donc 5 divise \(7(x - 1).\) Mais comme pgcd\((5\,; 7)=1,\) alors d’après le théorème de Gauss, 5 divise \(x - 1.\)

Il existe donc un entier \(k\) tel que \(x - 1 = 5k,\) d’où \(x = 5k + 1.\)

Ensuite, inutile de recommencer la même démonstration avec \(y,\) il suffit de remplacer.

\(7(5k + 1 - 1) = -5(y - 1)\)
\(⇔ y = -7k - 1\)

5- Soit \(k\) un entier.

\(7(5k + 1) + 5(-7k - 1) = 2\)
\(⇔ 35k + 7 - 35k - 5 = 2.\)

Quel que soit \(k,\) l’équation est toujours juste. Donc les solutions de (E) sont les couples \((5k + 1\,; -7k - 1).\)

Note : si nous avions choisi d’autres valeurs particulières, nous aurions trouvé d’autres couples identiques à celui-ci, par exemple \((5k + 6\,; -7k - 8).\)

Voir aussi les exercices sur équations diophantiennes et le petit théorème de Fermat.

 

couple solution