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

Ce cours de maths expertes de Terminale démontre l’identité de Bézout (démonstration exigible) et calcule des coefficients par l’algorithme d’Euclide étendu, puis énonce le théorème de Bézout sur les entiers premiers entre eux et démontre le théorème de Gauss et son corollaire. Il se termine par la résolution des équations diophantiennes ax + by = c, l’inverse modulo n et les systèmes de deux congruences.

Identité de Bézout et algorithme d’Euclide étendu

Ce qu’il faut savoir

Rappels (chapitre Divisibilité, division euclidienne et PGCD). L’algorithme d’Euclide enchaîne les divisions euclidiennes ( $a$ par $b$ , puis $b$ par le reste, et ainsi de suite) : le PGCD est le dernier reste non nul. Deux entiers sont premiers entre eux lorsque leur PGCD vaut $1$ . Dans tout le chapitre, les lettres désignent des entiers relatifs.

Identité de Bézout. Soit $a$ et $b$ deux entiers relatifs non tous deux nuls et $d = pgcd (a; b)$ . Il existe des entiers relatifs $u$ et $v$ tels que $a u + b v = d .$ Un tel couple $(u; v)$ est un couple de coefficients de Bézout de $a$ et $b$ . C’est une démonstration exigible du programme (ci-dessous).

Algorithme d’Euclide étendu. Pour obtenir $u$ et $v$ , on écrit l’algorithme d’Euclide, on isole chaque reste, puis on remonte : on part du dernier reste non nul et on remplace, ligne après ligne, chaque reste par son expression, jusqu’à n’avoir plus que $a$ et $b$ .

Pas d’unicité. Si $a u_{0} + b v_{0} = d$ , alors pour tout entier $k$ , le couple $(u_{0} + k \frac{b}{d}; v_{0} - k \frac{a}{d})$ convient aussi : il y a une infinité de couples de Bézout. On démontrera au cas 4 qu’il n’y en a pas d’autres.

Un peu d’histoire. La première démonstration connue est due à Claude-Gaspard Bachet de Méziriac, dans ses Problèmes plaisants et délectables (édition de 1624) ; Étienne Bézout (1730-1783) a ensuite étendu le résultat, notamment aux polynômes.

Exemples

Démonstration de l’identité de Bézout (exigible). Soit $E$ l’ensemble des entiers strictement positifs de la forme $a u + b v$ , avec $u$ et $v$ entiers. $E$ n’est pas vide : il contient $a \times a + b \times b = a^{2} + b^{2} > 0$ . Toute partie non vide de $ℕ$ ayant un plus petit élément, $E$ a un plus petit élément $m = a u_{0} + b v_{0}$ .

• $m$ divise $a$ . Écrivons la division euclidienne $a = m q + r$ avec $0 ⩽ r < m$ . Alors $r = a - q (a u_{0} + b v_{0})$ $= a (1 - q u_{0}) + b (- q v_{0})$ est de la forme $a u + b v$ . Si l’on avait $r > 0$ , $r$ serait un élément de $E$ strictement plus petit que $m$ : impossible. Donc $r = 0$ et $m$ divise $a$ . De même, $m$ divise $b$ .

• $m = d$ . $m$ est un diviseur commun positif de $a$ et $b$ , donc $m ⩽ d$ . Et $d$ divise $a$ et $b$ , donc il divise la combinaison $a u_{0} + b v_{0} = m$ ; comme $m > 0$ , $d ⩽ m$ . Ainsi $m = d$ : il existe bien $u_{0}$ et $v_{0}$ tels que $a u_{0} + b v_{0} = d$ . $∎$

Euclide étendu avec $a = 247$ et $b = 91$ .

Division euclidienne	Reste isolé
$247 = 2 \times 91 + 65$	$65 = 247 - 2 \times 91$
$91 = 1 \times 65 + 26$	$26 = 91 - 65$
$65 = 2 \times 26 + 13$	$13 = 65 - 2 \times 26$
$26 = 2 \times 13 + 0$	dernier reste non nul : $13$

Remontée, en partant de la dernière ligne utile : $13 = 65 - 2 \times 26$ $= 65 - 2 (91 - 65)$ $= 3 \times 65 - 2 \times 91$ $= 3 (247 - 2 \times 91) - 2 \times 91$ $= 3 \times 247 - 8 \times 91$ . Vérification : $741 - 728 = 13$ . Le couple $(3; - 8)$ est un couple de Bézout de $247$ et $91$ .

D’autres couples. Ici $\frac{b}{d} = \frac{91}{13} = 7$ et $\frac{a}{d} = \frac{247}{13} = 19$ : les couples $(3 + 7 k; - 8 - 19 k)$ conviennent, car $247 \times 7 k - 91 \times 19 k$ $= 1 729 k - 1 729 k$ $= 0$ . Pour $k = 1$ : $(10; - 27)$ , et $2 470 - 2 457 = 13$ .

Réflexe — J’écris l’algorithme d’Euclide en isolant chaque reste, puis je remonte depuis le dernier reste non nul en gardant $a$ et $b$ visibles : je ne regroupe que leurs coefficients. Je termine toujours par une vérification numérique.

Attention — Pendant la remontée, on n’effectue pas les produits : écrire $3 \times 65 = 195$ fait perdre la trace de $65$ , donc de $a$ et $b$ . Et on ne parle pas « du » couple de Bézout : deux copies peuvent donner des couples différents et justes.

1 / 5

Théorème de Bézout : entiers premiers entre eux

Ce qu’il faut savoir

Théorème de Bézout. Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement s’il existe des entiers relatifs $u$ et $v$ tels que $a u + b v = 1 .$ C’est une équivalence : pour prouver que deux entiers sont premiers entre eux, il suffit d’exhiber une combinaison qui vaut $1$ , sans calculer le PGCD.

Une combinaison qui ne vaut pas 1. Si $a u + b v = m$ avec $u$ et $v$ entiers, alors $pgcd (a; b)$ divise $m$ , mais il n’est pas forcément égal à $m$ . Seuls $m = 1$ et $m = - 1$ permettent de conclure (pour $- 1$ , on change les signes de $u$ et $v$ ).

Conséquences.

Si $d = pgcd (a; b) ⩾ 1$ , $a = d a'$ et $b = d b'$ , alors $a'$ et $b'$ sont premiers entre eux.
Si $a$ est premier avec $b$ et premier avec $c$ , alors $a$ est premier avec le produit $b c$ . Par récurrence, si $a$ est premier avec $b$ , il est premier avec toute puissance $b^{k}$ ( $k \in ℕ^{*}$ ).

Exemples

Démonstration du théorème. Si $pgcd (a; b) = 1$ , l’identité de Bézout donne $u$ et $v$ tels que $a u + b v = 1$ . Réciproquement, si $a u + b v = 1$ , tout diviseur commun positif de $a$ et $b$ divise la combinaison $a u + b v = 1$ : il vaut $1$ , donc $pgcd (a; b) = 1$ .

Sans calculer le PGCD. $13 \times 55 - 21 \times 34 = 715 - 714 = 1$ : d’après le théorème de Bézout, $55$ et $34$ sont premiers entre eux.

Pour tout entier $n$ . $3 (2 n + 3) - 2 (3 n + 4)$ $= 6 n + 9 - 6 n - 8$ $= 1$ . Cette égalité est de la forme $u (2 n + 3) + v (3 n + 4) = 1$ avec $u = 3$ et $v = - 2$ entiers : d’après le théorème de Bézout, $2 n + 3$ et $3 n + 4$ sont premiers entre eux pour tout entier $n$ .

Démonstration de la première conséquence. L’identité de Bézout donne $a u + b v = d$ , soit $d a' u + d b' v = d$ ; en divisant par $d \neq 0$ : $a' u + b' v = 1$ , et le théorème de Bézout conclut.

Démonstration de la deuxième. On écrit $a u + b v = 1$ et $a s + c t = 1$ , puis on multiplie membre à membre : $(a u + b v) (a s + c t) = 1$ , soit $a (a u s + u c t + b v s) + b c (v t) = 1$ . C’est une relation de Bézout entre $a$ et $b c$ . Pour les puissances : si $a$ est premier avec $b$ et avec $b^{k}$ , il l’est avec $b^{k} \times b = b^{k + 1}$ .

Réflexe — Pour montrer que deux entiers (ou deux expressions en $n$ ) sont premiers entre eux, je cherche des coefficients entiers qui donnent une combinaison égale à $1$ ou $- 1$ (pour éliminer $n$ , je croise les coefficients de $n$ ), puis je cite le théorème de Bézout.

Attention — « $a u + b v = d$ , donc $pgcd (a; b) = d$ » est faux en général : $4 \times 3 + 6 \times (- 1) = 6$ , alors que $pgcd (4; 6) = 2$ . Une combinaison donne seulement un multiple du PGCD ; seul le cas $1$ est une équivalence.

2 / 5

Théorème de Gauss et corollaire

Ce qu’il faut savoir

Théorème de Gauss. Si $a$ divise $b c$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$ . C’est une démonstration exigible du programme.

Corollaire. Si $a$ et $b$ divisent $c$ et si $a$ et $b$ sont premiers entre eux, alors $a b$ divise $c$ .

Écriture irréductible. Si $\frac{p}{q} = \frac{p'}{q'}$ avec $q > 0$ , $q' > 0$ , $pgcd (p; q) = 1$ et $pgcd (p'; q') = 1$ , alors $p = p'$ et $q = q'$ : un rationnel a une seule écriture sous forme de fraction irréductible à dénominateur positif.

Hypothèse indispensable. Sans « premiers entre eux », les deux résultats sont faux : on vérifie donc toujours que le PGCD vaut $1$ (par l’algorithme d’Euclide, une relation de Bézout ou les décompositions).

Exemples

Démonstration du théorème de Gauss (exigible). On suppose que $a$ divise $b c$ et que $pgcd (a; b) = 1$ . D’après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $a u + b v = 1$ . En multipliant par $c$ : $a c u + b c v = c$ . Or $a$ divise $a c u$ , et $a$ divise $b c$ , donc $b c v$ . Comme $a$ divise les deux termes, il divise leur somme $c$ . $∎$

Démonstration du corollaire. Comme $a$ divise $c$ , $c = a k$ avec $k$ entier. Alors $b$ divise $a k$ et $b$ est premier avec $a$ : par le théorème de Gauss, $b$ divise $k$ , soit $k = b k'$ . Donc $c = a b k'$ : $a b$ divise $c$ .

Démonstration de l’unicité de l’écriture irréductible. De $\frac{p}{q} = \frac{p'}{q'}$ on tire $p q' = p' q$ . Donc $q$ divise $p q'$ , et $q$ est premier avec $p$ : par Gauss, $q$ divise $q'$ . De même $q'$ divise $q$ . Deux entiers strictement positifs qui se divisent mutuellement sont égaux : $q = q'$ , puis $p = p'$ .

Appliquer Gauss. Si $9$ divise $4 n$ , comme $pgcd (9; 4) = 1$ (car $9 - 2 \times 4 = 1$ ), le théorème de Gauss donne : $9$ divise $n$ .

Appliquer le corollaire. Un entier divisible par $7$ et par $16$ est divisible par $7 \times 16 = 112$ , car $7 \times 7 - 3 \times 16 = 1$ : $7$ et $16$ sont premiers entre eux.

Deux contre-exemples. $6$ divise $3 \times 4 = 12$ , mais $6$ ne divise ni $3$ ni $4$ : ici $pgcd (6; 3) = 3 \neq 1$ . De même, $4$ et $6$ divisent $12$ , mais $24$ ne divise pas $12$ : $pgcd (4; 6) = 2$ .

Réflexe — Avant d’écrire « d’après le théorème de Gauss », j’écris la phrase « $a$ divise $b c$ et $pgcd (a; b) = 1$ » avec sa justification. Si le PGCD n’est pas $1$ , je simplifie d’abord par ce PGCD.

Attention — De « $12$ divise $8 n$ » on ne déduit pas « $12$ divise $n$ » : $pgcd (12; 8) = 4$ . On simplifie par $4$ : $8 n = 12 k$ donne $2 n = 3 k$ , donc $3$ divise $2 n$ , et comme $pgcd (3; 2) = 1$ , $3$ divise $n$ ( $n = 3$ convient sans que $12$ divise $n$ ).

3 / 5

Équations diophantiennes ax + by = c

Ce qu’il faut savoir

Définition. Une équation diophantienne linéaire est une équation $a x + b y = c$ dont on cherche les solutions $(x; y)$ dans $ℤ^{2}$ ( $a$ , $b$ , $c$ entiers donnés, $a$ et $b$ non nuls).

Existence. L’équation $a x + b y = c$ admet des solutions dans $ℤ^{2}$ si et seulement si $d = pgcd (a; b)$ divise $c$ .

Toutes les solutions. On écrit $a = d a'$ et $b = d b'$ ( $a'$ et $b'$ premiers entre eux). Si $(x_{0}; y_{0})$ est une solution, les solutions sont exactement les couples $(x_{0} + b' k; y_{0} - a' k), k \in ℤ .$

Méthode. 1. Je calcule $d$ et je teste si $d$ divise $c$ (sinon : aucune solution). 2. Je divise l’équation par $d$ : $a' x + b' y = c'$ . 3. Une relation de Bézout $a' u + b' v = 1$ , multipliée par $c'$ , donne une solution particulière. 4. Je soustrais, j’applique le théorème de Gauss, et je vérifie la réciproque.

Exemples

Démonstration de l’existence. Pour tous entiers $x$ et $y$ , $d$ divise $a$ et $b$ , donc $a x + b y$ : s’il y a une solution, $d$ divise $c$ . Réciproquement, si $c = d m$ , une relation de Bézout $a u + b v = d$ multipliée par $m$ donne $a (u m) + b (v m) = c$ .

Démonstration de la forme des solutions (application de Gauss). Si $(x; y)$ est solution, en soustrayant $a x_{0} + b y_{0} = c$ : $a (x - x_{0}) = b (y_{0} - y)$ , puis, en divisant par $d$ , $a' (x - x_{0}) = b' (y_{0} - y)$ . Ainsi $b'$ divise $a' (x - x_{0})$ , et $pgcd (a'; b') = 1$ : par Gauss, $b'$ divise $x - x_{0}$ , soit $x = x_{0} + b' k$ . En reportant, $a' b' k = b' (y_{0} - y)$ , d’où $y = y_{0} - a' k$ . Réciproquement, $a (x_{0} + b' k) + b (y_{0} - a' k)$ $= c + (a b' - b a') k$ $= c$ , car $a b' = d a' b' = b a'$ .

Réponse rédigée : résoudre $51 x + 21 y = 18$ . $51 = 2 \times 21 + 9$ , $21 = 2 \times 9 + 3$ , $9 = 3 \times 3$ : $pgcd (51; 21) = 3$ , qui divise $18$ . On divise par $3$ : $17 x + 7 y = 6$ . Bézout : $17 = 2 \times 7 + 3$ et $7 = 2 \times 3 + 1$ , donc $1 = 7 - 2 \times 3$ $= 7 - 2 (17 - 2 \times 7)$ $= 5 \times 7 - 2 \times 17$ . En multipliant par $6$ : $17 \times (- 12) + 7 \times 30 = 6$ . Si $(x; y)$ est solution, $17 (x + 12) = 7 (30 - y)$ ; $7$ divise $17 (x + 12)$ et $pgcd (7; 17) = 1$ , donc par Gauss $7$ divise $x + 12$ : $x = - 12 + 7 k$ , puis $y = 30 - 17 k$ . Réciproquement, $17 (- 12 + 7 k) + 7 (30 - 17 k)$ $= - 204 + 210$ $= 6$ . $S = {(- 12 + 7 k; 30 - 17 k), k \in ℤ} .$

Avec des entiers naturels. Pour la même équation, $x ⩾ 0$ impose $k ⩾ \frac{12}{7} \approx 1, 7$ , donc $k ⩾ 2$ , et $y ⩾ 0$ impose $k ⩽ \frac{30}{17} \approx 1, 8$ , donc $k ⩽ 1$ : aucune solution dans $ℕ^{2}$ .

Sans solution. $18 x + 24 y = 10$ : $pgcd (18; 24) = 6$ ne divise pas $10$ . En effet, $18 x + 24 y = 6 (3 x + 4 y)$ est toujours un multiple de $6$ .

Réflexe — PGCD, test de divisibilité, division par $d$ , solution particulière par Bézout, soustraction et Gauss, réciproque. Je donne l’ensemble $S$ avec « $k \in ℤ$ » et je vérifie une solution.

Attention — Le pas est $b' = \frac{b}{d}$ et $a' = \frac{a}{d}$ , pas $b$ et $a$ : pour $51 x + 21 y = 18$ , écrire $x = - 12 + 21 k$ ne donne qu’une solution sur trois. Et le théorème de Gauss s’applique à $a'$ et $b'$ , premiers entre eux, pas à $a$ et $b$ .

4 / 5

Inverse modulo n et systèmes de congruences

Ce qu’il faut savoir

Inverse modulo $n$ ( $n ⩾ 2$ ). Un entier $u$ est un inverse de $a$ modulo $n$ lorsque $a u \equiv 1 [n]$ . Critère : $a$ admet un inverse modulo $n$ si et seulement si $pgcd (a; n) = 1$ ; l’inverse est alors unique modulo $n$ . Pour un grand module, on le calcule par l’algorithme d’Euclide étendu.

Équation $a x \equiv b [n]$ . Si $pgcd (a; n) = 1$ et si $u$ est un inverse de $a$ , alors $a x \equiv b [n] ⟺ x \equiv u b [n]$ : une seule classe de solutions. Si $d = pgcd (a; n) ⩾ 2$ : pas de solution si $d$ ne divise pas $b$ ; sinon, on divise $a$ , $b$ et $n$ par $d$ (méthode du chapitre Congruences). Dans tous les cas, $a x \equiv b [n]$ équivaut à l’équation diophantienne $a x - n y = b$ , d’inconnues entières $x$ et $y$ .

Système de deux congruences. Si $p$ et $q$ sont premiers entre eux ( $p, q ⩾ 2$ ), le système $x \equiv α [p]$ et $x \equiv β [q]$ a des solutions, et elles forment une seule classe modulo $p q$ : si $x_{0}$ est une solution, les solutions sont les entiers $x \equiv x_{0} [p q]$ . Avec $p u + q v = 1$ , l’entier $x_{0} = α q v + β p u$ est une solution.

Exemples

Démonstration du critère. $a u \equiv 1 [n]$ équivaut à l’existence d’un entier $v$ tel que $a u + n v = 1$ : d’après le théorème de Bézout, un tel $u$ existe si et seulement si $pgcd (a; n) = 1$ . Unicité : si $a u \equiv 1$ et $a u' \equiv 1 [n]$ , alors $u \equiv u (a u') = (u a) u' \equiv u' [n]$ .

Inverse de $14$ modulo $45$ . $45 = 3 \times 14 + 3$ , $14 = 4 \times 3 + 2$ , $3 = 1 \times 2 + 1$ : $pgcd (14; 45) = 1$ . Remontée : $1 = 3 - 2$ $= 3 - (14 - 4 \times 3)$ $= 5 \times 3 - 14$ $= 5 (45 - 3 \times 14) - 14$ $= 5 \times 45 - 16 \times 14$ . Donc $14 \times (- 16) \equiv 1 [45]$ , et $- 16 \equiv 29 [45]$ : l’inverse de $14$ modulo $45$ est $29$ . Vérification : $14 \times 29 = 406 = 9 \times 45 + 1$ .

Réponse rédigée : $14 x \equiv 5 [45]$ . En multipliant par $29$ : $x \equiv 29 \times 5 = 145 [45]$ , soit $x \equiv 10 [45]$ . Réciproquement, $14 \times 10 = 140 = 3 \times 45 + 5$ . Les solutions sont les entiers $10 + 45 k$ , $k \in ℤ$ .

Sans solution. $6 x \equiv 4 [15]$ : si $6 x - 4 = 15 k$ , alors $4 = 6 x - 15 k = 3 (2 x - 5 k)$ , et $3$ diviserait $4$ . Aucune solution.

Démonstration pour le système. $q v = 1 - p u \equiv 1 [p]$ , donc $x_{0} = α q v + β p u$ $\equiv α \times 1 + 0$ $= α [p]$ ; de même $p u \equiv 1 [q]$ donne $x_{0} \equiv β [q]$ . Si $x$ est une autre solution, $p$ et $q$ divisent $x - x_{0}$ et sont premiers entre eux : par le corollaire de Gauss, $p q$ divise $x - x_{0}$ . Réciproquement, si $x \equiv x_{0} [p q]$ , alors $x \equiv x_{0}$ modulo $p$ et modulo $q$ , qui divisent $p q$ .

Réponse rédigée : $x \equiv 2 [9]$ et $x \equiv 5 [14]$ . $14 = 9 + 5$ , $9 = 5 + 4$ , $5 = 4 + 1$ , donc $1 = 5 - 4$ $= 2 \times 5 - 9$ $= 2 \times 14 - 3 \times 9$ : $u = - 3$ , $v = 2$ . Alors $x_{0} = 2 \times 14 \times 2 + 5 \times 9 \times (- 3)$ $= 56 - 135$ $= - 79$ , et $- 79 + 126 = 47$ . Les solutions sont les entiers $x \equiv 47 [126]$ . Contrôle : $47 = 5 \times 9 + 2 = 3 \times 14 + 5$ .

Réflexe — Pour un inverse : Euclide, remontée jusqu’à $a u + n v = 1$ , puis $u$ ramené entre $0$ et $n - 1$ . Pour $a x \equiv b [n]$ : je multiplie par l’inverse et je vérifie. Pour un système : relation de Bézout entre les modules, solution $x_{0}$ , puis classe modulo $p q$ .

Attention — L’inverse de $a$ n’est pas l’opposé $- a$ : c’est le $u$ tel que $a u \equiv 1 [n]$ , et il n’existe que si $pgcd (a; n) = 1$ . Le théorème des systèmes suppose les modules premiers entre eux ; sans cette hypothèse, il peut n’y avoir aucune solution : $x \equiv 1 [4]$ et $x \equiv 2 [6]$ n’a aucune solution (la première impose $x$ impair, la seconde $x$ pair).

5 / 5

Pour aller plus loin

Entiers premiers entre eux, PGCD d’expressions en $n$ . La définition, les fractions irréductibles et l’étude de $pgcd (A; B)$ quand $A$ et $B$ dépendent d’un entier $n$ (selon les valeurs de $n$ ) sont traitées dans le chapitre Divisibilité, division euclidienne et PGCD.

Équations de congruence pour un petit module. Chercher un inverse par essais, résoudre $a x \equiv b [n]$ à l’aide d’un tableau de restes ou en simplifiant par un diviseur commun : voir Congruences.

Lemme d’Euclide. Cas particulier du théorème de Gauss : si un nombre premier $p$ divise un produit $a b$ , alors $p$ divise $a$ ou $p$ divise $b$ (si $p$ ne divise pas $a$ , il est premier avec $a$ ). Ce lemme, l’unicité de la décomposition en facteurs premiers et le petit théorème de Fermat sont traités dans Nombres premiers.

À retenir

Identité de Bézout : il existe $u$ et $v$ entiers tels que $a u + b v = pgcd (a; b)$ ; on les obtient en remontant l’algorithme d’Euclide.
Théorème de Bézout : $a$ et $b$ sont premiers entre eux si et seulement s’il existe $u$ et $v$ entiers tels que $a u + b v = 1$ .
Théorème de Gauss : si $a$ divise $b c$ et $pgcd (a; b) = 1$ , alors $a$ divise $c$ . Corollaire : $a$ et $b$ premiers entre eux divisant $c$ donnent $a b$ qui divise $c$ .
$a x + b y = c$ a des solutions entières si et seulement si $d = pgcd (a; b)$ divise $c$ ; elles s’écrivent $(x_{0} + \frac{b}{d} k; y_{0} - \frac{a}{d} k)$ , $k \in ℤ$ .
$a$ est inversible modulo $n$ si et seulement si $pgcd (a; n) = 1$ ; alors $a x \equiv b [n] ⟺ x \equiv u b [n]$ , avec $u$ inverse de $a$ .

Questions fréquentes

Comment trouver des coefficients de Bézout ?

On écrit l’algorithme d’Euclide en isolant chaque reste, puis on remonte depuis le dernier reste non nul en remplaçant les restes un par un, sans effectuer les produits. Pour 31 et 9 : 31 = 3 × 9 + 4 et 9 = 2 × 4 + 1, donc 1 = 9 − 2 × 4 = 9 − 2(31 − 3 × 9) = 7 × 9 − 2 × 31. On vérifie toujours le résultat par un calcul direct.

Comment montrer que deux entiers sont premiers entre eux avec Bézout ?

Il suffit d’exhiber des entiers u et v tels que au + bv = 1 : c’est le théorème de Bézout, qui est une équivalence. Pour 3n + 2 et 4n + 3, on calcule 4(3n + 2) − 3(4n + 3) = −1, ce qui donne une combinaison égale à 1 en changeant les signes.

Que dit le théorème de Gauss ?

Si a divise bc et si a est premier avec b, alors a divise c. Par exemple, si 11 divise 4n, comme 3 × 4 − 11 = 1, 11 et 4 sont premiers entre eux et 11 divise n. Sans l’hypothèse « premiers entre eux », c’est faux : 14 divise 4 × 7 sans diviser 4 ni 7.

Comment résoudre une équation ax + by = c dans ℤ² ?

On vérifie que pgcd(a ; b) divise c, on divise l’équation par ce PGCD, on trouve une solution particulière avec une relation de Bézout, puis on soustrait et on applique le théorème de Gauss. Les solutions s’écrivent (x₀ + b′k ; y₀ − a′k), k entier, avec a′ et b′ les coefficients divisés par le PGCD.

Comment calculer un inverse modulo n ?

L’inverse de a modulo n existe si et seulement si pgcd(a ; n) = 1. On remonte l’algorithme d’Euclide jusqu’à au + nv = 1 : alors au ≡ 1 [n], et on ramène u entre 0 et n − 1. Par exemple 50 − 7 × 7 = 1 donne l’inverse de 7 modulo 50 : −7, soit 43.

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