Partner von azubiworld.com - Logo
 
Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » gcd(a, b)

gcd(a, b)

Universität / Fachhochschule

Kryptologie

Tags: Kryptologie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
t-bus

t-bus aktiv_icon

10:17 Uhr, 17.10.2019

Antworten
Die Aufgabe lautet: Seien a, b positive ganze Zahlen. Man zeige, dass die Anzahl der Iterationen des euklidischen Algorithmus und die Folge der Quotienten im euklidischen Algorithmus nur vom Quotienten a/b abhängt.
Die Lösung besagt: Die Bruchdarstellung einer rationalen Zahl ungleich 0 ist eindeutig, wenn man verlangt, dass der Nenner positiv und Nenner und Zähler teilerfremd sind. Daher genügt es zu zeigen, dass der euklidische Algorithmus angewandt auf a, b genauso viele Iterationen braucht wie der euklidische Algorithmus angewandt auf a/gcd(a, b) , b/gcd(a, b). Dies folgt aber aus der Konstruktion.

Aus dieser Aufgabe soll folgen, dass gcd(a, b) = rn = 1 ist. Hierbei ist rn das letzte Glied der Restefolge rk vor dem letzten Glied dieser Folge, welches 0 ist.
Betrachten wir gcd(100, 35) dann ist rn=5 und das ist doch ungleich 1??



Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."
Neue Frage
t-bus

t-bus aktiv_icon

10:30 Uhr, 17.10.2019

Antworten
Nun habe ich die Lösung einmal nachgerechnet und komme auch nicht auf die gleiche ANzahl von Iterationen ?

frage
Antwort
michaL

michaL aktiv_icon

10:44 Uhr, 17.10.2019

Antworten
Hallo,

und du willst uns verkaufen, dass der ggT(100;30)=5 ist?

Was studierst du nochmal?

Mfg Michael
t-bus

t-bus aktiv_icon

10:50 Uhr, 17.10.2019

Antworten
Ahh danke für den netten Hinweis ;-)
Habe den Fehler bemerkt ;-)

Trotzdem verstehe ich die Folgerung immer noch nicht.
Antwort
michaL

michaL aktiv_icon

10:52 Uhr, 17.10.2019

Antworten
Hallo,

kannst du nicht "der Einfachheit halber" einen Scan der Originalaufgabenstellung einstellen?

Mfg Michael
t-bus

t-bus aktiv_icon

10:59 Uhr, 17.10.2019

Antworten
Okay

Frage 2
Antwort
michaL

michaL aktiv_icon

11:47 Uhr, 17.10.2019

Antworten
Hallo,

ok, versuchen wir mal, Licht ins Dunkle zu bringen.

Wir betrachten zwei Zahlen a und b (der Einfachheit halber beide positiv und a>b), deren ggT größer ist als 1.

Also a>b>0, g:=ggT(a;b)>1.

Jetzt stellen wir einmal den Ablauf des euklidischen Algorithmus mit a und b einerseits und mit aʹ:=ag und bʹ:=bg andererseits einander gegenüber:
a÷b=q1 Rest r1 vs. aʹ÷bʹ=q1ʹ Rest r1ʹ

aʹ÷bʹ=q1ʹ Rest r1ʹ bedeutet ag=aʹ=bʹq1ʹ+r1ʹ=bgq1ʹ+r1ʹ mit anderen Worten ag=bgq1ʹ+r1ʹ.
Multiplziere mit g und erhalte a=bq1ʹ+r1ʹg.

Das vergleichen wir mit a=bq1+r1.
Die Zahl q1 entspricht dem Vorkommateil des Bruches ab (etwa als Dezimalbruch). Demnach muss gelten: q1ʹ=q1
Daraus folgt, dass r1ʹg=a-bq1ʹ=a-bq1=r1, also r1ʹg=r1 gilt.

Diesem Muster folgen alle weiteren Schritte (ja, für jemanden mit wenig mathematischer Erfahrung wäre es gut, das an einem konkreten Beispiel nachzuvollziehen): Die Quotienten sind immer gleich, die Quotienten der jeweiligen Reste sind stets gleich dem ggT g.

Kommst du nun mit der Sache klar?

Mfg Michael

t-bus

t-bus aktiv_icon

16:37 Uhr, 17.10.2019

Antworten
Leider nein..
ich weiß nicht, worauf du bzw. die Aufgabe hinaus möchte.
Antwort
michaL

michaL aktiv_icon

17:04 Uhr, 17.10.2019

Antworten
Hallo,

wir gehen von ab>0 mit a,b\0 aus.

Der euklidische Algorithmus erwirtschaftet ja ja der Reihe nach Quotienten qi und Reste ri, wobei die Obergrenze für i die Anzahl der Iterationen des Algorithmus darstellt.
Du bekommst also konkret(er):
a=q0b+r0
b=q1r0+r2

ri-2=qnri-1+ri

rn-2=qnrn-1+rn
wobei rn=0 das Ende des Algorithmus definiert. (Evtl. ist eure "Numerierung" der Reste anders, das hängt davon ab, ob man b als r0 "sehen" möchte.)

Man erwirtschaftet also durch den Algorithmus eine "Kette" von Paaren (qi;ri) (0in).

Ich verstehe die Aufgabe folgendermaßen:
Gilt ab=aʹbʹ, so sind die Folge der qiʹ und die Anzahl nʹ der Iterationen aus dem eukidischem Algorithmus zur Ermittlung des ggT(aʹ,bʹ) gleich der Folge der qi bzw. die Anzahl der Iterationen n aus dem eukidischem Algorithmus zur Ermittlung des ggT(a,b).

Die Folge der Quotienten und die Anzahl der notwendigen Iterationsschritte n hängen damit also nur vom Wert ab ab, nicht aber von der möglichen Tatsache, wie groß der ggT(a,b) konkret ist.

Eine Bitte: Wenn du die Aufgabenstellung nicht verstehst, gib das bitte nächstes Mal gleich zu Anfang bekannt. Dann kann man sich die Mathematik erst einmal sparen.

Mfg Michael
t-bus

t-bus aktiv_icon

16:50 Uhr, 21.10.2019

Antworten
Ich verstehe das die Anzahl der Iterationen gleich ist, aber warum gilt aus dieser Aufgabe gcd(a,b)=rn=1. ???
Bei uns ist rn das letzte von Null verschiedene Glied der Restefolge, welches im Fall gcd(100,35), r3= 5 ist und das ist offensichtlich ungleich 1.
Berechne ich jedoch den gcd(100/5, 35/5) dann ist hier r3=1.

Irgendwie verwirrt mich die Schreibweise. Es wird so geschrieben, weil man anschließend die Aussage rn=1 in einem Beweis benötigt.

frage 4
t-bus

t-bus aktiv_icon

16:50 Uhr, 21.10.2019

Antworten
Ich verstehe das die Anzahl der Iterationen gleich ist, aber warum gilt aus dieser Aufgabe gcd(a,b)=rn=1. ???
Bei uns ist rn das letzte von Null verschiedene Glied der Restefolge, welches im Fall gcd(100,35), r3= 5 ist und das ist offensichtlich ungleich 1.
Berechne ich jedoch den gcd(100/5, 35/5) dann ist hier r3=1.

Irgendwie verwirrt mich die Schreibweise. Es wird so geschrieben, weil man anschließend die Aussage rn=1 in einem Beweis benötigt.

frage 4
Antwort
ledum

ledum aktiv_icon

21:51 Uhr, 21.10.2019

Antworten
hallo
da steht doch, dass es sich bei ab um gekürzte Brüche handelt:"eindeutig, wenn man verlangt, dass der Nenner positiv und Nenner und Zähler teilerfremd sind. und dann ist natürlich der gcd1
Gruß ledum
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.