Ressources · Terminale · Maths expertes (option Tle)

Théorèmes de Bézout et de Gauss

Identité de Bézout démontrée et algorithme d’Euclide étendu, théorème de Bézout et entiers premiers entre eux, théorème de Gauss et son corollaire, équations diophantiennes ax + by = c, inverse modulo n et systèmes de deux congruences.

À propos de cette page

Cinq problèmes corrigés d’arithmétique : chargement d’une palette, algorithme d’Euclide étendu en Python, deux récipients non gradués, jetons comptés par paquets de 8 et de 11, racines rationnelles d’un polynôme à coefficients entiers.

5 problèmes, du plus simple au plus difficile. Écris tes réponses, puis « Vérifier ».

Résoudre un problème : la méthode

Je traduis l’énoncé : une masse, une recette ou un volume total donne une équation ax + by = c ; des restes donnent des congruences.
Je prépare l’outil : algorithme d’Euclide, relation de Bézout vérifiée, PGCD égal à 1 justifié avant tout « d’après Gauss ».
Je résous dans ℤ (ou ℤ²) avec la réciproque, avant de tenir compte des contraintes concrètes.
J’applique les contraintes (entiers naturels, intervalle, minimum) en encadrant le paramètre k.
Je réponds dans les termes de l’énoncé : un chargement, un nombre de jetons, une suite d’opérations, et je vérifie une solution.

Problème 1 · Chargement d’une palette★★★Facile

Un atelier expédie deux modèles de colis : le modèle A pèse

7

kg et le modèle B pèse

11

kg. Une palette doit porter exactement

200

kg de colis. On note

x

le nombre de colis A et

y

le nombre de colis B, entiers naturels : la masse totale vaut

7 x + 11 y

, d’où l’équation

(E)

7 x + 11 y = 200

1. Couple $(u; v)$ tel que $7 u + 11 v = 1$ avec $- 11 < u < 0$ : $u$ =
$11 = 7 + 4$ ; $7 = 4 + 3$ ; $4 = 3 + 1$ : $pgcd (7; 11) = 1$ . Remontée : $1 = 4 - 3 = 4 - (7 - 4) = 2 \times 4 - 7 = 2 (11 - 7) - 7 = 2 \times 11 - 3 \times 7$ . Donc $u = - 3$ .
2. Pour ce couple, $v$ =
$7 \times (- 3) + 11 \times 2 = - 21 + 22 = 1$ .
3. Démontrer que les solutions de $(E)$ dans $ℤ^{2}$ sont les couples $(- 600 + 11 k; 400 - 7 k)$ , $k \in ℤ$ . Plus petit entier $k$ pour lequel $x ⩾ 0$ :
Rédaction attendue. En multipliant la relation de Bézout par $200$ : $7 \times (- 600) + 11 \times 400 = 200$ . Si $(x; y)$ est solution, $7 (x + 600) = 11 (400 - y)$ ; $11$ divise $7 (x + 600)$ et $pgcd (11; 7) = 1$ , donc par le théorème de Gauss $11$ divise $x + 600$ : $x = - 600 + 11 k$ . En reportant, $7 \times 11 k = 11 (400 - y)$ , d’où $y = 400 - 7 k$ . Réciproquement, $7 (- 600 + 11 k) + 11 (400 - 7 k) = - 4 200 + 4 400 = 200$ . Enfin $- 600 + 11 k ⩾ 0$ équivaut à $k ⩾ \frac{600}{11} \approx 54, 5$ : le plus petit est $k = 55$ .
4. Nombre de chargements possibles de la palette :
$y = 400 - 7 k ⩾ 0$ équivaut à $k ⩽ \frac{400}{7} \approx 57, 1$ . Donc $k \in {55; 56; 57}$ , ce qui donne $(5; 15)$ , $(16; 8)$ et $(27; 1)$ . Vérifications : $35 + 165 = 200$ ; $112 + 88 = 200$ ; $189 + 11 = 200$ .
5. L’atelier veut manipuler le moins de colis possible. Nombre total de colis du chargement choisi :
Les totaux valent $5 + 15 = 20$ , $16 + 8 = 24$ et $27 + 1 = 28$ . Le minimum est $20$ colis : $5$ colis A et $15$ colis B. C’est le chargement qui contient le plus de colis lourds (modèle B) : pour une masse fixée, plus les colis sont lourds, moins il en faut.

Problème 2 · L’algorithme d’Euclide étendu en Python★★★Moyen

On considère les deux fonctions Python suivantes, où a, b et n sont des entiers naturels non nuls (l’affectation de la boucle est simultanée).

def bezout(a, b):
  r, u, v = a, 1, 0
  rp, up, vp = b, 0, 1
  while rp != 0:
    q = r // rp
    r, u, v, rp, up, vp = rp, up, vp, r - q*rp, u - q*up, v - q*vp
  return (r, u, v)

def inverse_mod(a, n):
  r, u, v = bezout(a, n)
  if r != 1:
    return None
  return u % n

1. Pour l’appel bezout(143, 52), nombre de passages dans la boucle while :
Valeurs des variables avant la boucle et après chaque passage :
Passage q r u v rp up vp
avant $143$ $1$ $0$ $52$ $0$ $1$
$1$ $2$ $52$ $0$ $1$ $39$ $1$ $- 2$
$2$ $1$ $39$ $1$ $- 2$ $13$ $- 1$ $3$
$3$ $3$ $13$ $- 1$ $3$ $0$ $4$ $- 11$
Après le troisième passage, rp vaut $0$ : la boucle s’arrête.
2. Cet appel renvoie le triplet (r, u, v). Valeur de v :
Le triplet renvoyé est $(13; - 1; 3)$ . Vérification : $143 \times (- 1) + 52 \times 3 = - 143 + 156 = 13$ , et l’algorithme d’Euclide ( $143 = 2 \times 52 + 39$ , $52 = 39 + 13$ , $39 = 3 \times 13$ ) confirme que $pgcd (143; 52) = 13$ .
3. Démontrer que les égalités $r = a u + b v$ et $r p = a \cdot u p + b \cdot v p$ sont vraies avant la boucle et le restent après chaque passage. Pour l’appel bezout(143, 52), valeur de $143 \times u p + 52 \times v p$ à la sortie de la boucle :
Rédaction attendue. Avant la boucle : $a \times 1 + b \times 0 = a = r$ et $a \times 0 + b \times 1 = b = r p$ . Supposons les deux égalités vraies au début d’un passage. Les nouvelles valeurs de r, u, v sont les anciennes rp, up, vp : la première égalité reste vraie. Et la nouvelle valeur de rp est $r - q \cdot r p = (a u + b v) - q (a \cdot u p + b \cdot v p) = a (u - q \cdot u p) + b (v - q \cdot v p)$ : la seconde reste vraie avec les nouvelles up et vp. À la sortie, $r p = 0$ : $143 \times 4 + 52 \times (- 11) = 572 - 572 = 0$ .
4. Justifier que la boucle s’arrête toujours et que la valeur r renvoyée est $pgcd (a; b)$ . Valeur de r renvoyée par bezout(91, 35) :
Rédaction attendue. Les valeurs successives de rp sont les restes de l’algorithme d’Euclide : à chaque passage, la nouvelle valeur $r - q \cdot r p$ est le reste de la division de r par rp, donc un entier naturel strictement inférieur à rp. Une suite d’entiers naturels strictement décroissante ne peut pas être infinie : la boucle s’arrête. À la sortie, r est le dernier reste non nul, c’est-à-dire le PGCD, et l’invariant donne $r = a u + b v$ . Pour $91$ et $35$ : $91 = 2 \times 35 + 21$ , $35 = 21 + 14$ , $21 = 14 + 7$ , $14 = 2 \times 7$ : le PGCD vaut $7$ .
5. Valeur renvoyée par l’appel inverse_mod(34, 143) :
$143 = 4 \times 34 + 7$ ; $34 = 4 \times 7 + 6$ ; $7 = 6 + 1$ : $pgcd (34; 143) = 1$ et l’inverse existe. Remontée : $1 = 7 - 6 = 7 - (34 - 4 \times 7) = 5 \times 7 - 34 = 5 (143 - 4 \times 34) - 34 = 5 \times 143 - 21 \times 34$ . Donc $34 \times (- 21) \equiv 1 [143]$ , et u % n ramène $- 21$ à $- 21 + 143 = 122$ . Vérification : $34 \times 122 = 4 148 = 29 \times 143 + 1$ . Le test r != 1 traduit le critère : $a$ est inversible modulo $n$ si et seulement si $pgcd (a; n) = 1$ .

Passage	`q`	`r`	`u`	`v`	`rp`	`up`	`vp`
avant		$143$	$1$	$0$	$52$	$0$	$1$
$1$	$2$	$52$	$0$	$1$	$39$	$1$	$- 2$
$2$	$1$	$39$	$1$	$- 2$	$13$	$- 1$	$3$
$3$	$3$	$13$	$- 1$	$3$	$0$	$4$	$- 11$

Problème 3 · Deux récipients non gradués★★★Moyen

On dispose d’une réserve d’eau, d’une cuve et de deux récipients non gradués de

17

litres et de

5

litres. Une opération consiste soit à verser dans la cuve un récipient rempli à la réserve, ce qui ajoute sa contenance, soit à remplir un récipient avec l’eau de la cuve et à le vider dans l’évier, ce qui retire sa contenance. Si l’on ajoute (ou retire)

| x |

fois

17

litres et

| y |

fois

5

litres, le volume obtenu est

17 x + 5 y

litres, en

| x | + | y |

opérations (

x

y

entiers relatifs, négatifs pour un retrait). On admet que l’ordre des opérations peut toujours être choisi pour que la cuve contienne assez d’eau à chaque retrait.

1. Justifier que $17$ et $5$ sont premiers entre eux. Couple $(u; v)$ tel que $17 u + 5 v = 1$ avec $u = - 2$ : $v$ =
Rédaction attendue. $17 = 3 \times 5 + 2$ ; $5 = 2 \times 2 + 1$ ; $2 = 2 \times 1 + 0$ : le dernier reste non nul vaut $1$ , donc $pgcd (17; 5) = 1$ . Remontée : $1 = 5 - 2 \times 2 = 5 - 2 (17 - 3 \times 5) = 7 \times 5 - 2 \times 17$ : $(u; v) = (- 2; 7)$ , et $- 34 + 35 = 1$ .
2. En déduire une suite d’opérations qui donne exactement $1$ litre dans la cuve. Nombre d’opérations de la suite obtenue avec ce couple :
On verse sept fois le récipient de $5$ L ( $35$ L), puis on retire deux fois $17$ L : il reste $35 - 34 = 1$ litre. Cela fait $7 + 2 = 9$ opérations.
3. Résoudre dans $ℤ^{2}$ l’équation $17 x + 5 y = 3$ , puis déterminer le nombre minimal d’opérations pour obtenir $3$ litres :
Rédaction attendue. $pgcd (17; 5) = 1$ divise $3$ . En multipliant la relation de Bézout par $3$ : $17 \times (- 6) + 5 \times 21 = 3$ . Si $(x; y)$ est solution, $17 (x + 6) = 5 (21 - y)$ ; $5$ divise $17 (x + 6)$ et $pgcd (5; 17) = 1$ , donc par Gauss $x = - 6 + 5 k$ , puis $y = 21 - 17 k$ ; la réciproque se vérifie. $S = {(- 6 + 5 k; 21 - 17 k), k \in ℤ}$ . Nombre d’opérations $| x | + | y |$ : pour $k ⩽ 0$ , $| y | = 21 - 17 k ⩾ 21$ ; pour $k ⩾ 2$ , $| y | ⩾ 13$ et $| x | ⩾ 4$ , soit au moins $17$ ; pour $k = 1$ , $(x; y) = (- 1; 4)$ et $1 + 4 = 5$ . Le minimum est $5$ opérations : quatre fois $5$ L versés, une fois $17$ L retirés ( $20 - 17 = 3$ ).
4. On remplace les récipients par des récipients de $12$ L et de $20$ L. Démontrer que tout volume obtenu est un multiple de $4$ . Plus petit volume strictement positif réalisable :
Rédaction attendue. Tout volume obtenu s’écrit $12 x + 20 y = 4 (3 x + 5 y)$ , avec $3 x + 5 y$ entier : c’est un multiple de $4$ . Et $4$ est réalisable : $12 \times 2 + 20 \times (- 1) = 4$ (deux fois $12$ L versés, une fois $20$ L retirés). Le plus petit volume strictement positif est donc $4$ litres ; un volume impair est impossible.
5. Soit $a$ et $b$ deux entiers naturels non nuls et $d = pgcd (a; b)$ . Démontrer que les volumes réalisables avec des récipients de $a$ L et $b$ L sont exactement les multiples de $d$ . Plus petit volume strictement positif réalisable avec des récipients de $21$ L et $35$ L :
Rédaction attendue. Notons $V = {a x + b y, (x; y) \in ℤ^{2}}$ . D’une part, $d$ divise $a$ et $b$ , donc $a x + b y$ : tout élément de $V$ est un multiple de $d$ . D’autre part, l’identité de Bézout donne $a u + b v = d$ ; pour un multiple $m = d j$ , $a (u j) + b (v j) = m$ appartient à $V$ . Par double inclusion, $V$ est l’ensemble des multiples de $d$ . Pour $21$ et $35$ : $35 = 21 + 14$ , $21 = 14 + 7$ , $14 = 2 \times 7$ , donc $d = 7$ .

Problème 4 · Compter des jetons★★★Difficile

Une réserve contient

N

jetons,

N

entier naturel. Rangés par paquets de

8

, il en reste

3

; rangés par paquets de

11

, il en reste

5

. On a donc

N \equiv 3 [8]

N \equiv 5 [11]

1. Plus petit entier naturel vérifiant ces deux conditions :
Les entiers congrus à $3$ modulo $8$ sont $3$ , $11$ , $19$ , $27$ … Leurs restes modulo $11$ valent $3$ , $0$ , $8$ et $5$ : le premier qui convient est $27$ ( $27 = 3 \times 8 + 3 = 2 \times 11 + 5$ ).
2. Démontrer qu’un entier $N$ vérifie les deux conditions si et seulement si $N$ est congru modulo $88$ à l’entier trouvé à la question précédente. Couple $(u; v)$ tel que $8 u + 11 v = 1$ avec $u = - 4$ : $v$ =
Rédaction attendue. $8 \times (- 4) + 11 \times 3 = - 32 + 33 = 1$ , donc $pgcd (8; 11) = 1$ (Bézout). Si $N$ vérifie les deux conditions, $N - 27 \equiv 0 [8]$ et $N - 27 \equiv 0 [11]$ , car $27$ les vérifie aussi : $8$ et $11$ divisent $N - 27$ et sont premiers entre eux, donc par le corollaire de Gauss, $88$ divise $N - 27$ . Réciproquement, si $N = 27 + 88 k$ , comme $88 = 8 \times 11$ , $N \equiv 27 \equiv 3 [8]$ et $N \equiv 27 \equiv 5 [11]$ .
3. Nombre de jetons, sachant qu’il est compris entre $500$ et $600$ :
$500 ⩽ 27 + 88 k ⩽ 600$ équivaut à $\frac{473}{88} ⩽ k ⩽ \frac{573}{88}$ , soit environ $5, 4 ⩽ k ⩽ 6, 5$ : $k = 6$ et $N = 27 + 528 = 555$ . Vérification : $555 = 69 \times 8 + 3 = 50 \times 11 + 5$ .
4. Le responsable affirme qu’un autre lot laisse $4$ jetons par paquets de $12$ et $1$ jeton par paquets de $8$ . Démontrer que c’est impossible. Reste modulo $4$ imposé par la première condition :
Rédaction attendue. Supposons $M \equiv 4 [12]$ et $M \equiv 1 [8]$ . De $M = 4 + 12 k$ , on tire $M \equiv 0 [4]$ , car $4$ divise $4$ et $12$ . De $M = 1 + 8 j$ ( $j$ entier), on tire $M \equiv 1 [4]$ , car $4$ divise $8$ . On aurait $0 \equiv 1 [4]$ : absurde. Le corollaire de Gauss ne s’applique pas ici, car $pgcd (12; 8) = 4 \neq 1$ .
5. Soit $p, q ⩾ 2$ premiers entre eux, $α$ et $β$ des entiers, et $N_{0}$ une solution du système $N \equiv α [p]$ , $N \equiv β [q]$ . Démontrer que les solutions sont exactement les entiers congrus à $N_{0}$ modulo $p q$ . Nombre de solutions comprises entre $0$ et $p q - 1$ :
Rédaction attendue. Si $N$ est solution, $N - N_{0} \equiv α - α = 0 [p]$ et $N - N_{0} \equiv 0 [q]$ : $p$ et $q$ divisent $N - N_{0}$ et sont premiers entre eux, donc $p q$ divise $N - N_{0}$ (corollaire de Gauss). Réciproquement, si $N - N_{0} = p q k$ , c’est un multiple de $p$ et de $q$ , donc $N \equiv N_{0} \equiv α [p]$ et $N \equiv β [q]$ . Entre $0$ et $p q - 1$ , il y a exactement un entier de cette classe : une seule solution, comme $27$ entre $0$ et $87$ .

Problème 5 · Racines rationnelles d’un polynôme à coefficients entiers★★★Difficile

On considère

P (x) = 3 x^{3} + 4 x^{2} - 5 x - 2

. On cherche ses racines rationnelles. Soit

r = \frac{p}{q}

une racine rationnelle de

P

, écrite sous forme irréductible :

p \in ℤ

q \in ℕ^{*}

pgcd (p; q) = 1

1. Démontrer que $3 p^{3} + 4 p^{2} q - 5 p q^{2} - 2 q^{3} = 0$ , puis que $p$ divise $2$ . Nombre de valeurs possibles de $p$ :
Rédaction attendue. $P (\frac{p}{q}) = 0$ ; en multipliant par $q^{3} \neq 0$ : $3 p^{3} + 4 p^{2} q - 5 p q^{2} - 2 q^{3} = 0$ . Donc $2 q^{3} = p (3 p^{2} + 4 p q - 5 q^{2})$ : $p$ divise $2 q^{3}$ . Comme $p$ est premier avec $q$ , il est premier avec $q^{3}$ (conséquence du théorème de Bézout) ; le théorème de Gauss donne : $p$ divise $2$ . Ainsi $p \in {- 2; - 1; 1; 2}$ : $4$ valeurs.
2. Démontrer de même que $q$ divise $3$ . Nombre de rationnels candidats $\frac{p}{q}$ :
Rédaction attendue. $3 p^{3} = q (- 4 p^{2} + 5 p q + 2 q^{2})$ : $q$ divise $3 p^{3}$ . Comme $q$ est premier avec $p$ , donc avec $p^{3}$ , le théorème de Gauss donne : $q$ divise $3$ , soit $q \in {1; 3}$ . Les candidats sont $\pm 1$ , $\pm 2$ , $\pm \frac{1}{3}$ et $\pm \frac{2}{3}$ : $8$ rationnels distincts.
3. Nombre de racines rationnelles de $P$ :
On teste les $8$ candidats : $P (1) = 3 + 4 - 5 - 2 = 0$ ; $P (- 2) = - 24 + 16 + 10 - 2 = 0$ ; $P (- \frac{1}{3}) = - \frac{1}{9} + \frac{4}{9} + \frac{15}{9} - \frac{18}{9} = 0$ . Les cinq autres donnent $P (- 1) = 4$ , $P (2) = 28$ , $P (\frac{1}{3}) = - \frac{28}{9}$ , $P (\frac{2}{3}) = - \frac{8}{3}$ , $P (- \frac{2}{3}) = \frac{20}{9}$ . Trois racines rationnelles ; comme $P$ est de degré $3$ , il n’en a pas d’autre.
4. Plus petite racine de $P$ :
Les racines sont $- 2$ , $- \frac{1}{3}$ et $1$ , et $P (x) = (x - 1) (3 x + 1) (x + 2)$ : en développant, $(x - 1) (3 x^{2} + 7 x + 2) = 3 x^{3} + 4 x^{2} - 5 x - 2$ .
5. Démontrer que $Q (x) = x^{3} - 3 x - 1$ n’a aucune racine rationnelle. Valeur de $Q (- 1)$ :
Rédaction attendue. Si $\frac{p}{q}$ irréductible ( $q ⩾ 1$ ) est racine, $p^{3} - 3 p q^{2} - q^{3} = 0$ . Alors $p$ divise $q^{3}$ et $q$ divise $p^{3}$ ; avec $pgcd (p; q) = 1$ , le même raisonnement (Gauss) donne $p$ divise $1$ et $q$ divise $1$ : les seuls candidats sont $1$ et $- 1$ . Or $Q (1) = 1 - 3 - 1 = - 3$ et $Q (- 1) = - 1 + 3 - 1 = 1$ : aucun n’est racine, donc $Q$ n’a pas de racine rationnelle.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs