Théorème de Bézout et algorithme d'Euclide étendu

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Bézout : PGCD(a ; b) = 1 il existe (u, v) Z^2 tel que au + bv = 1. • Il existe toujours (u, v) tel que au + bv = PGCD(a ; b) ; on l'obtient en remontant l'algorithme d'Euclide. • ax + by = c admet des solutions entières si et seulement si PGCD(a ; b) divise c. • Si au + bv = 1, alors bv 1 a : v est un inverse de b modulo a.

Le cours

Théorème de Bézout (fondamental) Soient a et b deux entiers relatifs non tous deux nuls. a et b sont premiers entre eux (PGCD(a ; b) = 1) si et seulement si il existe deux entiers relatifs u et v tels que : au + bv = 1 Une relation de la forme au + bv = PGCD(a ; b) s'appelle une identité de Bézout. Algorithme d'Euclide étendu : détermination de coefficients de Bézout Pour trouver un couple d'entiers (u ; v) tel que au + bv = 1, on effectue l'algorithme d'Euclide jusqu'au reste 1, puis on « remonte » les égalités en isolant chaque reste successif. Généralisation Pour tous entiers relatifs a et b non tous nuls de PGCD(a ; b) = d, il existe des entiers relatifs u et v tels que au + bv = d. L'ensemble des combinaisons linéaires \ax + by (x, y) Z^2\ est exactement l'ensemble des multiples de d (dZ).

Dans ce chapitre