„Przepełnienie” w rozszerzonym algorytmie euklidesowym

Przepraszam, jeśli mylę się z miejscem zadawania pytania (może powinienem przejść do stackoverflow.com/mathoverflow.net?).

Ciekawe, jeśli istnieje dowód, że podczas oceny rozszerzony algorytm euklidesową współczynnikom Bézout użytkownika (to jest y i T w tożsamość jako + Bt = GCD ( , b )) nie przekracza około rozsądne wartości (w zależności od a, b, chyba ). W szczególności implementacji w języku programowania ogólnego interesuje mnie poprawność przepełnienia programu.

Mówiąc dokładniej, mogę wspomnieć, że korzystam z opisu algorytmu Victora Shoupa (4.2 w jego książce „ A Obliczeniowe wprowadzenie do teorii liczb i algebry ” bezpłatnie dostępnej na jego stronie głównej).

Nazywa się to tożsamością / lematem Bézouta (nie mylić z twierdzeniem Bézouta w geometrii algebraicznej), który stwierdza:

Lemat. Dla każdej liczby całkowitej , dla niektórych liczb całkowitych . Możemy również założyći.$a,b \neq 0$$\gcd(a,b) = ax + by$$x,y$$|x| \leq |b|$$|y| \leq |a|$

Dowody mogą być oparte na standardowych podręcznikach algebry. Możesz także sam to udowodnić przez indukcję iteracji procesu gcd.

Zasadniczo jest to prawdą w każdej domenie euklidesowej z multiplikatywną funkcją euklidesową . W tym przypadku, gdy , mamyktóry jest multiplikatywny.$R$$f$$R = \mathbf{Z}$$f(x) = |x|$