"Überlauf" im erweiterten euklidischen Algorithmus

11

Es tut mir leid, wenn ich mich mit dem Ort irre, an dem ich die Frage stellen kann (vielleicht sollte ich zu stackoverflow.com/mathoverflow.net gehen?).

Ich frage mich, ob es einen Beweis dafür gibt, dass bei der Bewertung des erweiterten euklidischen Algorithmus die Bézout-Koeffizienten (dh s und t in der Identität als + bt = gcd ( a , b )) einige vernünftige Werte nicht überschreiten werden (abhängig von a, b, denke ich ). Insbesondere die Implementierung in einer universellen Programmiersprache interessiert mich für die Überlaufkorrektheit des Programms.

Um genau zu sein, kann ich erwähnen, dass ich Victor Shoups Beschreibung des Algorithmus verwende (4.2 in seinem Buch „ Eine rechnergestützte Einführung in die Zahlentheorie und Algebra “, das auf seiner Homepage frei verfügbar ist).

Artem Pelenitsyn
quelle
1
Ich denke, das liegt definitiv im Rahmen.
Suresh Venkat

Antworten:

13

Dies nennt man die Identität / das Lemma von Bézout (nicht zu verwechseln mit dem Satz von Bézout in der algebraischen Geometrie), in dem es heißt:

a,b0gcd(a,b)=ax+byx,y|x||b||y||a|

Beweise können in Standard-Algebra-Lehrbüchern gefunden werden. Sie können es auch selbst beweisen, indem Sie die Iterationen des GCD-Prozesses einführen.

Im Allgemeinen gilt dies für jede euklidische Domäne mit einer multiplikativen euklidischen Funktion . In dem Fall hier, in dem , haben wirdas ist multiplikativ.RfR=Zf(x)=|x|

Hsien-Chih Chang 張顯 之
quelle
Sie verweisen auf Wikipedia, aber es gibt keine solchen Wörter: "Wir können auch annehmen ...". Würden Sie bitte ein „Standard-Algebra-Lehrbuch“ nennen? Ich habe mir Rotmans ersten Kurs in abstrakter Algebra angesehen: Es gibt eine Beschreibung von Eukl. Algo, aber es gibt keine solchen Grenzen für Koeffizienten. Dieselbe Geschichte in Shoups Buch, auf das ich in meinem Beitrag verwiesen habe.
Artem Pelenitsyn
2
Versuchen Sie Theorem 2.5 im Buch von Keijo Ruohonen, math.tut.fi/~ruohonen/MC.pdf . Wenn meine Mutterschaft richtig ist, hat das Buch von Fraleign das Lemma im Haupttext oder in den Übungen. amazon.com/First-Course-Abstract-Algebra-7th/dp/0201763907
Hsien-Chih Chang 張顯 之
1
Kann das verallgemeinert werden? Angenommen, es gibt eine Lösung für so dass? gcd(a1,,an)=ixiaii|xi|i|ai|
Chao Xu