Algorithme d'Euclide - Définition

Algorithme étendu aux coefficients de Bézout

L'identité de Bézout assure l'existence de deux entiers u et v tels que : au + bv = a_{N + 1} = PGCD(a,b). L'algorithme d'Euclide convenablement adapté permet de calculer de tels coefficients.

Description

Pour cela, on introduit deux suites (u_n) et (v_n) telles que pour tout n, on ait la relation : au_n + bv_n = a_n. Si de telles suites existent, les termes u_{N + 1},v_{N + 1} constitueront une paire de coefficients de Bezout pour a et b.

On peut choisir u₀ = 1,v₀ = 0 puis u₁ = 0,v₁ = 1, puis la relation de récurrence de pas 2 entre les a_n montre :

a_{n + 2} = a_n − q_{n + 2}a_{n + 1} = au_n + bv_n − q_{n + 2}(au_{n + 1} + bv_{n + 1}) = a(u_n − q_{n + 2}u_{n + 1}) + b(v_n − q_{n + 2}v_{n + 1})

On peut ainsi définir (u_n) par la relation de récurrence de pas 2 : u_{n + 2} = u_n − q_{n + 2}u_{n + 1} et l'initialisation précédente, et (v_n) par v_{n + 2} = v_n − q_{n + 2}v_{n + 1} et l'initialisation précédente ; et on obtient bien la relation annoncée pour tout n.

Commentaires

L'algorithme étendu s'implémente comme l'algorithme classique ; il suffit de rajouter des variables correspondant aux coefficients u et v à calculer, et de faire une multiplication et une soustraction supplémentaires, pour calculer chacun des deux nouveaux coefficients, à chaque étape.