Entiers de Bézout

Soient a et b deux entiers relatifs tous deux non nuls, d leur PGCD. Il existe deux entiers relatifs u et v tels que:
d=ua+bv
preuve: C'est tout simplement parce que d est (par définition même) un générateur de aℤ+bℤ
Le résultat (très important) ci-dessus est connu sous le nom de 'théorème de Bézout' ou ' Identité de Bézout' , mais la première preuve en fut donnée par Bachet de Méziriac.
les entiers u et v s'appellent des 'entiers de Bézout' associés à a et b.
La réciproque est fausse!
(On peut écrire 4=2×8-2×6 et 4 n'est pas le pgcd de 6 et 8)
Claude-Gaspard
Bachet de Méziriac
(1581/1638-FR) 		Etienne Bézout
(1750/1783-FR)

Remarquons d'abord que:
Les couples d'entiers de Bézout sont en nombre infini.

Considérons l'équation:
xa+yb= 0
Elle a comme solution évidente le couple (u,v)=(b/d,-a/d)  où d=pgcd(a,b) ainsi que tous les multiples de ce couple, c'est à dire les couples de la forme (kb/d,-ka/d)=(ku,kv).
Ce sont d'ailleurs les seules solutions entières, en effet si
u'a+v'b=0
On en déduit que:
v'ua+vv'b=0
vu'a+vv'b=0
donc  v'u-u'v=0 donc v'u=u'v
Comme v est premier avec u  v divise v', v'=kv
Comme u est premier avec v  u divise u', u'=hu
donc kvu=huv soit (h-k)uv=0.
Si u=0 alors (u',v')=k(u,v)
Si v=0 alors (u',v')=h(u,v)
Enfin si u ≠ 0 et v ≠ 0 alors uv ≠ 0 et h=k
Cela étant vu si (u,v) est un couple d'entiers de Bézout pour (a,b) et si (x,y) est une solution de xa+yb=0 alors (u+x,v+y) est un autre couple d'entiers de Bézout pour (a,b). Ce qui justifie notre assertion que les couples de Bézout sont en nombre infini.

Algorithme de détermination

Se pose alors le problème de la détermination pratique des entiers de Bézout. L'algorithme d'Euclide fournit une solution.
Supposons d'abord que a soit un multiple de b disons a=bd alors pgcd(a,b)=b, un couple de Bézout est (0,1)
Supposons maintenant que a et b ne soient pas multiples l'un de l'autre on sait que pgcd(a,b) = pgcd(b,c= a%b)
Si b et c sont multiples l'un de l'autre c est le pgcd de a et b donc
a=bq1 +c (la division euclidienne) donne c=a-bq1 qui  est une relation de Bézout on peut donc prendre comme solution (1,-q1).
Si maintenant b et c ne sont pas multiples l'un de l'autre, on poursuit l'algorithme
pgcd(a,b)=pgcd(b,c) = pgcd(c,d) où d =b%c
Si c est un multiple de d on part de :
d=b-cq2 puis on remplace c par a-bq1 de la sorte on obtient: d=b-(a-bq1)q2 et ainsi de suite...On peut donc prendre comme solution (-q2,1+q1q2)
En résumé on va construire une suite récurrente double (rn) avec:
Une autre suite (qn) où qn est le quotient de rn-2 par rn-1
Deux suites récurrentes doubles un et vn où
un+1=un-1-qn+1un
vn+1=vn-1-qn+1vn
On arrête le processus dès que rn+1 divise rn les entiers de Bézout sont alors (un,vn)
Vous pouvez maintenant générer quelques exemples:
Donner deux entiers 0 <  m,n ≤ 100000   m: n:
PGCD de m et n et entiers de Bézout correspondants:
Message d'erreur éventuel:

Café Python

Ce programme utilise l'algorithme précédent.