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 42x + 26y = 2. Elle est résolue en page 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

Et 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)
= 1 302 – 1 300 = 2

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 (x0 ; y0) solution de (E).
  3. Montrer que (E) a les mêmes solutions que (E’) : 7(x – x0) = -5(y – y0)
  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é 1

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

Donc 2x ≡ 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 7x0 + 5y0 = 2

On remplace : 7x + 5y = 7x0 + 5y0

7(x – x0) = -5(y – y0)

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).