Quiz : Théorème de Bézout

Correction :

Le théorème de Bézout s'applique aux entiers relatifs (et aussi aux polynômes, mais ce n'est pas le contexte de ce quiz).

Correction :

C'est la formulation exacte de l'identité de Bézout : $au + bv = \text{PGCD}(a, b)$.

Correction :

Si $a$ et $b$ sont premiers entre eux, leur PGCD est 1. L'identité de Bézout devient donc $au + bv = 1$.

Correction :

On vérifie : $5 \times 3 + 7 \times (-2) = 15 - 14 = 1$. Il existe d'autres solutions, mais celle-ci est la plus simple.

Correction :

Comme 6 est le PGCD de 12 et 18, il existe des solutions. De plus, si $(u_0, v_0)$ est une solution, alors $(u_0 + 3k, v_0 - 2k)$ est aussi une solution pour tout entier relatif $k$. Il y a donc une infinité de solutions.

Correction :

C'est la réciproque (partielle) du théorème de Bézout : Si une combinaison linéaire de $a$ et $b$ vaut 1, alors $a$ et $b$ sont premiers entre eux.

Correction :

Non, car $\text{PGCD}(6, 9) = 3$, et 3 ne divise pas 2. Le théorème de Bézout nous dit qu'une équation de la forme $ax + by = c$ a des solutions entières si et seulement si $c$ est un multiple du PGCD de $a$ et $b$.

Correction :

Les coefficients $u$ et $v$ dans l'identité de Bézout sont des *entiers relatifs*. Ils peuvent être positifs, négatifs ou nuls.

Correction :

Attention, piège ! On ne peut *rien* conclure sur $\text{PGCD}(u, v)$ à partir de $au + bv = 1$. Par exemple, $2(5) + 3(-3) = 1$ , mais $PGCD(5,-3) = 1$, alors que $2(8) + 3(-5) = 1$, mais PGCD(8, -5) =1. On sait que PGCD(a,b) = 1. Il faut se méfier des "fausses réciproques". Cependant si on prend a = 7 et b= 11 alors 7(-3) + 11(2) = 1 et dans ce cas PGCD(-3, 2)=1 .

Correction :

L'algorithme d'Euclide étendu est une extension de l'algorithme d'Euclide qui permet non seulement de calculer le PGCD de deux entiers, mais aussi de trouver les coefficients *u* et *v* de l'identité de Bézout.

Correction :

En essayant les différentes options, on trouve que $25 \times 1 + 15 \times (-1) = 25 - 15 = 10 \neq 5$.

On peut utiliser l'algorithme d'Euclide étendu, mais on peut remarquer que $25 = 5 \times 5$ et $15 = 5 \times 3$. L'équation se simplifie en $5u + 3v = 1$. Une solution est $u = -1$ et $v = 2$, mais ce n'est pas dans les options. En revanche, on peut diviser l'équation de base par PGCD(25,15) =5 et on cherche donc $u$ et $v$ tels que $5u + 3v =1$. Une solution évidente est $u=2$ et $v=-3$, en multipliant cette solution par -1 on a : $u=-2$ et $v=3$. Finalement une solution de $25u + 15v = 5$ est donc $u=-2$ et $v=3$, ce qui n'apparait pas non plus dans les propositions... En revanche si on prend $u=1$ et $v=-1$ on a bien $25(1) + 15(-1) = 10$. Donc une infinité de solutions sont du type : $u= 1-3k$ et $v=-1+5k$. Si on prend $k=1$ on trouve $u=-2$ et $v= 4$ et on a bien $25(-2)+15(4) = -50 + 60 = 10$.

$25 = 15 \times 1 + 10$
$15 = 10 \times 1 + 5$
$10 = 5 \times 2 + 0$
On remonte : $5 = 15 - 10$
$5 = 15 - (25 - 15) = 15 \times 2 - 25$
$5 = 25 \times (-1) + 15 \times 2$ Donc $u = -1$ et $v=2$ est bien *une* solution (mais il y en a une infinité).

Correction :

Non, pas toujours. Il faut que $c$ soit un *multiple* du PGCD de $a$ et $b$. Si $c$ est strictement plus grand que le PGCD, mais pas un multiple, il n'y a pas de solution. Par exemple, $2x + 4y = 3$ n'a pas de solution entière, car $\text{PGCD}(2, 4) = 2$, et 3 n'est pas un multiple de 2.

Correction :

Soit $d=PGCD(a,b)$. Si $(x_0, y_0)$ est une solution particulière de $ax + by = c$, alors l'ensemble des solutions est donné par : $x = x_0 + \frac{b}{d}k$ et $y = y_0 - \frac{a}{d}k$, où $k$ est un entier relatif quelconque.

Correction :

Oui, c'est une application directe du théorème de Bézout. Si $u$ et $v$ sont premiers entre eux, leur PGCD est 1, et donc il existe des entiers $a$ et $b$ (qui ne sont pas uniques) tels que $au + bv = 1$.

Correction :

Calculons le PGCD(147, 258) : $258 = 147 \times 1 + 111$
$147 = 111 \times 1 + 36$
$111 = 36 \times 3 + 3$
$36 = 3 \times 12 + 0$
Donc PGCD(147, 258) = 3. Comme 3 divise 3, l'équation a des solutions entières (une infinité).

Correction :

On utilise l'algorithme d'Euclide étendu (voir question précédente) :
$3 = 111 - 36 \times 3$
$3 = 111 - (147 - 111) \times 3 = 111 \times 4 - 147 \times 3$
$3 = (258 - 147) \times 4 - 147 \times 3 = 258 \times 4 - 147 \times 7$
$3 = 147 \times (-7) - 258 \times (-4)$. Donc $x = -7$ et $y = -4$ est une solution particulière. En multipliant la solution précédente par -12 on trouve bien $x=-84-1 = -85$ et $y=-48$

Correction :

C'est la formule générale pour les solutions d'une équation diophantienne : si $(x_0, y_0)$ est une solution particulière, et si $d = \text{PGCD}(a, b)$, alors toutes les solutions sont de la forme $x = x_0 + \frac{b}{d}k$, $y = y_0 - \frac{a}{d}k$, où $k$ est un entier relatif quelconque.

Correction :

Pour se ramener à une équation où les coefficients de $x$ et $y$ sont premiers entre eux, il faut diviser $a$, $b$, et $c$ par le PGCD de $a$ et $b$. On obtient alors une équation équivalente de la forme $a'x + b'y = c'$, où $\text{PGCD}(a', b') = 1$.

Correction :

C'est une conséquence directe du théorème de Bézout. Si $ax + by = c$ a des solutions, alors tout diviseur commun de $a$ et $b$ divise aussi $c$. En particulier, $\text{PGCD}(a, b)$ divise $c$.

Correction :

Oui. La deuxième équation est obtenue en divisant la première par 2 (qui est le PGCD des coefficients de la première équation). Diviser une équation diophantienne par le PGCD des coefficients des inconnues donne une équation équivalente (même ensemble de solutions).

Correction :

Il y a une infinité de solutions. Une solution évidente est $x=0$, $y=0$. Plus généralement, comme PGCD(5,3)=1, on peut appliquer la formule générale. Les solutions sont de la forme $x = 3k$, $y = -5k$, où $k$ est un entier relatif quelconque.

Correction :

Non. Le PGCD de 10 et 15 est 5. Or, 7 n'est pas un multiple de 5. Donc, d'après le théorème de Bézout, il n'existe pas de solutions entières.

Correction :

Non, pas nécessairement. Contre-exemple : $6 \times 2 + 9 \times (-1) = 3 = \text{PGCD}(6, 9)$, mais 2 et -1 sont premiers entre eux. Autre contre-exemple : $6 \times 5 + 9 \times (-3) = 3$, mais $\text{PGCD}(5, -3) = 1$. Il n'y a pas de lien direct entre le fait que $au+bv = \text{PGCD}(a,b)$ et le fait que $u$ et $v$ soient premiers entre eux.

Correction :

L'énoncé correct du théorème de Bézout (avec l'équivalence) est : "$a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers relatifs $u$ et $v$ tels que : $au + bv = 1$". Il est important de noter que c'est une équivalence (si et seulement si) et que $u$ et $v$ sont des entiers *relatifs* (pas nécessairement naturels).

Correction :

L'équation $12x + 18y = 5$ n'a pas de solution entière. $\text{PGCD}(12, 18) = 6$, et 6 ne divise pas 5. Les autres équations ont des solutions car le PGCD des coefficients divise le terme constant.

Correction :

Vrai. Si $au + bv = 1$, alors $au \equiv 1 \pmod{b}$, donc $u$ est l'inverse de $a$ modulo $b$. De même, $bv \equiv 1 \pmod{a}$, donc $v$ est l'inverse de $b$ modulo $a$.

Correction :

L'algorithme d'Euclide étendu repose sur les divisions euclidiennes successives (comme l'algorithme d'Euclide classique). La clé est ensuite de *remonter* les calculs pour exprimer le PGCD comme combinaison linéaire de $a$ et $b$.

Correction :

On commence par multiplier l'équation de Bezout : 23 * (-8) + 37 * 5 = 1 par 2. On obtient alors une solution particulière : x0 = -16 et y0 = 10. Puis on applique le théorème pour trouver la forme générale des solutions à partir d'une solution particulière. x = -16 + 37k , y = 10 - 23k, où k est un entier relatif quelconque.

Correction :

Oui, toujours. Si $7x_0 + 11y_0 = 1$, alors $7(x_0 + 11) + 11(y_0 - 7) = 7x_0 + 77 + 11y_0 - 77 = 7x_0 + 11y_0 = 1$. C'est une application de la méthode pour trouver toutes les solutions à partir d'une solution particulière.

Correction :

La première étape est toujours de calculer le PGCD de 231 et 245. Si le PGCD ne divise pas 7, il n'y a pas de solution. Si le PGCD divise 7, alors on divise toute l'équation par le PGCD, et on se ramène à une équation où les coefficients sont premiers entre eux. On peut alors utiliser l'algorithme d'Euclide étendu pour trouver une solution particulière, puis la formule générale pour trouver toutes les solutions.