«Débordement» dans l'algorithme euclidien étendu

Désolé si je me trompe avec l'endroit où poser la question (peut-être que je devrais aller sur stackoverflow.com/mathoverflow.net?).

Je me demande s'il y a une preuve que lors de l'évaluation de l'algorithme euclidien étendu, les coefficients de Bézout (c'est-à-dire s et t dans l'identité comme + bt = gcd ( a , b )) ne dépasseront pas certaines valeurs raisonnables (selon a, b, je suppose ). En particulier, l'implémentation d'un langage de programmation à usage général m'intéresse à l'exactitude du débordement du programme.

Pour être précis, je peux mentionner que j'utilise la description de Victor Shoup de l'algorithme (4.2 dans son livre " A Computational Introduction to Number Theory and Algebra " disponible gratuitement sur sa page d'accueil).

C'est ce qu'on appelle l' identité / le lemme de Bézout (à ne pas confondre avec le théorème de Bézout en géométrie algébrique), qui déclare:

Lemme. Pour chaque entier , pour certains entiers . De plus, nous pouvons supposer queet.$a,b \neq 0$x , y | x | ≤ | b | | y | ≤ | a $\gcd(a,b) = ax + by$$x,y$$|x| \leq |b|$$|y| \leq |a|$

Les preuves peuvent être fondées dans des manuels d'algèbre standard. Vous pouvez également le prouver vous-même par induction sur les itérations du processus gcd.

En général, cela est vrai dans tout domaine euclidien avec une fonction euclidienne multiplicative . Dans le cas ici où , nous avonsce qui est multiplicatif.f R = Z f ( x ) = | x $R$$f$$R = \mathbf{Z}$$f(x) = |x|$