«Переполнение» в расширенном евклидовом алгоритме

Извините, если я ошибаюсь с местом, чтобы задать вопрос (может быть, я должен пойти на stackoverflow.com/mathoverflow.net?).

Интересно, есть ли доказательство того, что при оценке расширенного евклидова алгоритма коэффициенты Безу ( т. Е. S и t в тождестве как + bt = gcd ( a , b )) не будут превышать некоторые разумные значения (в зависимости от a, b, я полагаю ). В частности, реализация на каком-то универсальном языке программирования меня интересует корректность переполнения программы.

Чтобы быть точным, я могу упомянуть, что я использую описание алгоритма Виктора Шупа (4.2 в его книге « Вычислительное введение в теорию чисел и алгебру », свободно доступной на его домашней странице).

Это называется тождество / леммой Безу (не путать с теоремой Безу в алгебраической геометрии), которая гласит:

Лемма. Для любых целых чисел , для некоторых целых чисел . Также мы можем предположить, чтои,$a,b \neq 0$$\gcd(a,b) = ax + by$$x,y$$|x| \leq |b|$$|y| \leq |a|$

Доказательства можно найти в стандартных учебниках по алгебре. Также вы можете доказать это самостоятельно по индукции на процессах gcd.

В общем случае это верно для любой евклидовой области с мультипликативной евклидовой функцией . В случае, когда , мы имеемкоторый является мультипликативным.$R$$f$$R = \mathbf{Z}$$f(x) = |x|$