„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).

ds.algorithms nt.number-theory

— Artem Pelenitsyn
źródło

Myślę, że to zdecydowanie wchodzi w zakres.

— Suresh Venkat,

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|$

— Hsien-Chih Chang 張顯之
źródło

Odwołujesz się do Wikipedii, ale nie ma takich słów: „Możemy też założyć ...”. Czy mógłby Pan wymienić „standardowy podręcznik algebry”? Zajrzałem do pierwszego kursu Rotmana w algebrze abstrakcyjnej: jest opis Eucla. Algo, ale nie ma takich granic współczynników. Ta sama historia w książce Shoup, do której odniosłem się w moim poście.

— Artem Pelenitsyn,

Spróbuj Twierdzenie 2.5 w książce Keijo Ruohonen, math.tut.fi/~ruohonen/MC.pdf . Jeśli moja chwila jest prawidłowa, książka Fraleign ma lemat w tekście głównym lub w ćwiczeniach. amazon.com/First-Course-Abstract-Algebra-7th/dp/0201763907

— Hsien-Chih Chang 2 之

Czy można to uogólnić? powiedzmy, że istnieje rozwiązanie takie, że?

gcd (a_{1}, \dots, a_{n}) = \sum_{i} x_{i} a_{i}

$\gcd(a_1,\ldots,a_n) = \sum_{i} x_ia_i$

\sum_{i} | x_{i} | \leq \sum_{i} | a_{i} |

$\sum_{i}|x_i|\leq \sum_{i}|a_i|$

— Chao Xu