Le théorème de Bézout affirme que les entiers a et b sont premiers entre eux (si et) seulement si l’équation au + bv = 1 admet au moins une solution.
L’algorithme d’Euclide, permet de trouver de façon efficace les entiers u et v.
Je m’intéresse à la preuve de ce théorème et à l’implémentation de l’algorithme d’Euclide en C.
Preuve : Comme il s’agit d’une équivalence ( <=>, si et seulement si), la preuve se fait en 2 temps.
- a,b premiers entre eux => il existe un couple (u,v) tq : au + bv = 1
Rappelons que 2 nombres premiers entre eux, ont pour pgcd 1.
Donc dans notre cas, pgcd(a,b) = 1
Rappelons aussi l’égalité de Bézout :
- a,b deux entiers non nuls, D=pgcd(a,b)
- Il existe un couple (u,v) d’entiers relatifs tq :
au + bv = D
Puisque pgcd(a,b) = 1, l’égalité de Bézout permet de montrer qu’il existe bien un couple (u,v) tq au + bv = 1
Cette démonstration est un peu « facile » car j’utilise l’égalité de Bézout pour montrer le théorème de Bézout, le mieux serait de faire cette preuve, sans avoir recours aux outils donnés par Bézout.
1.2) a,b premiers entre eux => il existe un couple (u,v) tq : au + bv = 1
On suppose a,b premiers entre eux, donc pgcd(a,b) =1
pgcd(a,b) = 1; donc au moins un des entiers a,b est non nul
- Soit E l’ensemble des entiers de la forme au + bv, avec u et v des entiers.
- E est un ensemble non vide (car un des entiers a,b est non nul), de plus E contient un plus petit élément m, tq :
- m = au1 + bv1.
- La division euclidienne de a par m s’écrit : a = mq + r, avec r ∈ N. ( 0 <= r < m)
- On a alors : a = (au1 + bv1)q + r
- Donc : r = a – (au1 + bv1)q
- Donc : r = a (1-u1q) + b (-v1q)
- On voit bien que r est de la forme : r = au +bv
- Comme m est le plus petit élément de E, et que 0 <= r < m, on conclu donc que r = 0
r = 0 signifie que a est divisible par m
De la même manière, on démontre que b est divisible par m.
Donc m est un diviseur commun pour a, b, comme ils sont premiers entre eux, alors on déduit que m (qui est de la forme au +bv) = 1.
2) il existe un couple (u,v) tq : au + bv = 1 => a,b premiers entre eux
- Posons pgcd(a,b) = D, D divise a, et D divise b, D divise aussi au + bv.
- Ici nous avons au + bv = 1, donc D divise 1, donc D = 1.
- D =1, signifie que a,b sont bien premiers entre eux
Une autre façon de faire cette démonstration est de passer par sa contraposée, c’est à dire :
a,b ne sont pas premiers entre eux => il n’existe pas de couple (u,v) tq au + bv = 1
a,b non premiers entre eux, alors pgcd(a,b) = D, avec D > 1.
- D divise a, et D divise b, D divise aussi au +bv.
- 1 étant un nombre premier, son seul diviseur est lui même (1).
- D > 1, donc D ne divise pas 1, donc il n’existe pas de couple (u,v) tq au + bv = 1
Code C :