Erweiterter euklidischer Algorithmus-Vielfachsummendarstellung?
Hi, ich verstehe noch nicht ganz warum der EEA unendlich viele Vielfachsummendarstellungen hat? Kann mir jemand dies verständlich ( :) ) erklären?
Gruß
Kann es sein, dass du den ggT meinst?
Ja und davon die Vielfachsummendarstellung : g = xa + yb
1 Antwort
Sei g=ggT(a,b) und x,y sodass xa+yb=g
Dann folgt:
(x+nb)a + (y-na)b = ax+by+nba-nab = ax+by=g
für alle ganzen Zahlen n.
Du kannst also auf x ein vielfaches von b addieren und auf y das selbe vielfachen von a abziehen, und du erhälst wieder eine Paar, mit der du die Vielfachsummendarstellung erhälst.
Also ich habe hier ja noch die Variable n drin. Für jede beliebige ganze Zahl die du da einsetzt erhälst du jeweils ein unterschiedliches Zahlenpaar.
Und da es unendlich viele Ganze Zahlen gibt, gibt es eben auch unendlich viele Möglichkeiten
und wie genau kommt man drauf, dass dies passiert wenn man ein. vielfaches von b auf x addiert und ein vielfaches von a von y subtrahiert?
ahh und dann immer so weiter also damit ist dann die Unendlichkeit gezeigt, weil ich immer wieder ein neues paar bilden kann?