Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » gcd(a, b)

gcd(a, b)

Universität / Fachhochschule

Kryptologie

Tags: Kryptologie

anonymous

10:17 Uhr, 17.10.2019

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."

anonymous

10:30 Uhr, 17.10.2019

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

michaL aktiv_icon

10:44 Uhr, 17.10.2019

Hallo,

und du willst uns verkaufen, dass der

ggT (100; 30) = 5

ist?

Was studierst du nochmal?

Mfg Michael

anonymous

10:50 Uhr, 17.10.2019

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

Trotzdem verstehe ich die Folgerung immer noch nicht.

michaL aktiv_icon

10:52 Uhr, 17.10.2019

Hallo,

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

Mfg Michael

anonymous

10:59 Uhr, 17.10.2019

Okay

michaL aktiv_icon

11:47 Uhr, 17.10.2019

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 ʹ := \frac{a}{g}

und

b ʹ := \frac{b}{g}

andererseits einander gegenüber:

a \div b = q_{1}

Rest

r_{1}

vs.

a ʹ \div b ʹ = q_{1} ʹ

Rest

r_{1} ʹ

a ʹ \div b ʹ = q_{1} ʹ

Rest

r_{1} ʹ

bedeutet

\frac{a}{g} = a ʹ = b ʹ \cdot q_{1} ʹ + r_{1} ʹ = \frac{b}{g} \cdot q_{1} ʹ + r_{1} ʹ

mit anderen Worten

\frac{a}{g} = \frac{b}{g} \cdot q_{1} ʹ + r_{1} ʹ

.
Multiplziere mit

g

und erhalte

a = b \cdot q_{1} ʹ + r_{1} ʹ g

.

Das vergleichen wir mit

a = b \cdot q_{1} + r_{1}

.
Die Zahl

q_{1}

entspricht dem Vorkommateil des Bruches

\frac{a}{b}

(etwa als Dezimalbruch). Demnach muss gelten:

q_{1} ʹ = q_{1}

Daraus folgt, dass

r_{1} ʹ g = a - b \cdot q_{1} ʹ = a - b \cdot q_{1} = r_{1}

, also

r_{1} ʹ g = r_{1}

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

anonymous

16:37 Uhr, 17.10.2019

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

michaL aktiv_icon

17:04 Uhr, 17.10.2019

Hallo,

wir gehen von

a \geq b > 0

mit

a, b \in ℕ \ 0

aus.

Der euklidische Algorithmus erwirtschaftet ja ja der Reihe nach Quotienten

q_{i}

und Reste

r_{i}

, wobei die Obergrenze für

i

die Anzahl der Iterationen des Algorithmus darstellt.
Du bekommst also konkret(er):

a = q_{0} \cdot b + r_{0}

b = q_{1} \cdot r_{0} + r_{2}

⋮

r_{i - 2} = q_{n} \cdot r_{i - 1} + r_{i}

⋮

r_{n - 2} = q_{n} \cdot r_{n - 1} + r_{n}

wobei

r_{n} = 0

das Ende des Algorithmus definiert. (Evtl. ist eure "Numerierung" der Reste anders, das hängt davon ab, ob man

b

als

r_{0}

"sehen" möchte.)

Man erwirtschaftet also durch den Algorithmus eine "Kette" von Paaren

(q_{i}; r_{i})

(

0 \leq i \leq n

).

Ich verstehe die Aufgabe folgendermaßen:
Gilt

\frac{a}{b} = \frac{a ʹ}{b ʹ}

, so sind die Folge der

q_{i} ʹ

und die Anzahl

n ʹ

der Iterationen aus dem eukidischem Algorithmus zur Ermittlung des

ggT (a ʹ, b ʹ)

gleich der Folge der

q_{i}

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

\frac{a}{b}

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

anonymous

16:50 Uhr, 21.10.2019

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.

anonymous

16:50 Uhr, 21.10.2019

ledum aktiv_icon

21:51 Uhr, 21.10.2019

hallo
da steht doch, dass es sich bei

\frac{a}{b}

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

gcd 1

Gruß ledum

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1483179

1482534

	Status: nicht eingeloggt	Noch nicht registriert?