“Overflow” dalam Algoritma Euclidean yang Diperpanjang

Maaf jika saya salah dengan tempat untuk mengajukan pertanyaan (mungkin saya harus pergi ke stackoverflow.com/mathoverflow.net?).

Saya ingin tahu apakah ada bukti bahwa ketika mengevaluasi algoritma Euclidean yang diperluas, koefisien Bézout (yaitu s dan t dalam identitas sebagai + bt = gcd ( a , b )) tidak akan melebihi beberapa nilai wajar (tergantung pada a, b, saya kira ). Secara khusus implementasi pada beberapa bahasa pemrograman tujuan umum saya tertarik pada kebenaran melimpah program.

Untuk lebih tepatnya saya dapat menyebutkan bahwa saya menggunakan deskripsi algoritma algoritma Victor Shoup (4.2 dalam bukunya " A Pengantar Komputasi untuk Teori Angka dan Aljabar " tersedia secara bebas dari beranda).

Ini disebut identitas / lemma Bézout (jangan dikelirukan dengan teorema Bézout dalam geometri aljabar), yang menyatakan:

$a,b \neq 0$x , y | x | ≤ | b | | y | ≤ | a $\gcd(a,b) = ax + by$$x,y$$|x| \leq |b|$$|y| \leq |a|$

Bukti dapat ditemukan dalam buku teks aljabar standar. Anda juga dapat membuktikannya sendiri dengan induksi pada iterasi proses gcd.

Secara umum ini benar di setiap domain Euclidean dengan fungsi Euclidean multiplikasi . Dalam kasus di sini ketika , kita memilikiyang multiplikatif.f R = Z f ( x ) = | x $R$$f$$R = \mathbf{Z}$$f(x) = |x|$