Le théorème de Bezout

Identité de Bezout

Soient a et b deux entiers relatifs et d leur PGCD alors il existe deux entiers u et v tels que a·u + b·v = d.

Théorème de Bezout

Soient a et b deux entiers relatifs non nuls.
a et b sont premiers entre eux si et seulement si il existe deux entiers u et v tels que a·u + b·v = 1.

Résolution d'une équation diophantienne

Soient a, b et c des entiers, et d le PGCD de a et b, alors l'équation a·u + b·v = c admet des solutions entières si et seulement si c est un multiple de d.

Exemples de résolution

Si une équation diophantienne (c'est-à-dire que les nombres cherchés doivent être des entiers) a une solution unique, elle peut se calculer grâce à l'algorithme d'Euclide étendu ci-dessous (il est un peu différent de celui que l'on a déjà vu):

Problème

Résoudre a·u + b·v = c (trouver u et v entiers)

Algorithme de résolution

r_-2 := b; r_-1 := a; u_-2 := 0; u_-1 := 1; v_-2 := 1; v_-1 := a div b
k := -1
Tant que r_k > 0 faire
   Début
      k := k + 1
      r_k-2 = q_k·r_k-1 + r_k (avec q_k = r_k-2 div r_k-1 et r_k = r_k-2 mod r_k-1)
      u_k := u_k-2 - q_k·u_k-1
      v_k := v_k-2 - q_k·v_k-1
      On a la relation: r_k = a·u_k + b·v_k
   Fin
u = u_k-1·q_k
v = v_k-1·q_k

Le programme javascript ci-dessous permet de déterminer (s'il existe) le couple (u, v) solution de l'équation a·u + b·v = c (prendre a > b).

Référence

Dubertret Gilles, Initiation à la cryptographie, Vuibert Informatique, 2000, chapitre 3.

Didier Müller, 27.9.03