Zeigen Sie, dass ggt(a,b)=ggt(a,a+b)

Question

Text erkannt:

Bestimmen Sie \( a, b \in \mathbb{Z} \) mit dem erweiterten euklidischen Algorithmus, sodass \( \operatorname{ggT}(437,95)=437 a+95 b \).
b Seien \( a, b \in \mathbb{N} \). Zeigen Sie, dass \( \operatorname{ggT}(a, b)=\operatorname{ggT}(a, a+b) \).

Problem/Ansatz:

a) habe ich gelöst

Bei b ist meine Frage ob der Ansatz stimmt:

Der größte gemeinsame Teiler (ggT) zweier Zahlen ist die größte positive Zahl, die sowohl a als auch b ohne Rest teilt.

Sei d der ggT von a und b. Das bedeutet, dass d sowohl a als auch b ohne Rest teilt. Das können wir mathematisch wie folgt ausdrücken:

a = dx
b = dy

Dabei sind x und y ganze Zahlen.

Wir wollen nun zeigen, dass ggT(a, b) = ggT(a, a+b) ist. Das bedeutet, dass der ggT von a und b gleich dem ggT von a und a+b ist.

Sei e der ggT von a und a+b. Das bedeutet, dass e sowohl a als auch a+b ohne Rest teilt. Das können wir mathematisch wie folgt ausdrücken:

a = ez
a+b = ey

Dabei sind z und y ganze Zahlen.

Um zu zeigen, dass ggT(a, b) = ggT(a, a+b) gilt, müssen wir zeigen, dass d = e ist.

Wir wissen, dass a+b = a+dx = a(1+x). Da a sowohl a als auch a+b ohne Rest teilt, muss a auch a(1+x) ohne Rest teilen. Das bedeutet, dass a den ggT von a und a+b teilt.

Da d der ggT von a und b ist, teilt d sowohl a als auch b ohne Rest. Das bedeutet, dass d auch a(1+x) ohne Rest teilt.

Da sowohl d als auch e a(1+x) ohne Rest teilen, müssen d und e den gleichen ggT haben.

Daher gilt ggT(a, b) = ggT(a, a+b).

Answer 1

Du hast im Prinzip einfach nur etwas schwammig formuliert, dass ein gemeinsamer Teiler von \((a,b)\) auch ein gemeinsamer Teiler von \((a,a+b)\) ist. Das ginge etwas leichter, da wenn \(a=cx,b=cy\), dann ist \(a+b=c(x+y)\). Das ist also nicht das Problem. Am Ende machst du auch eine etwas komische Argumentation, von der ich nicht ganz verstehe, was sie soll.

Der \(\text{ggT}\) ist die größte Zahl mit dieser Eigenschaft, das ist der springende Punkt und hast du meiner Meinung nach nirgendwo gezeigt. Jenachdem, was du über den \(\text{ggT}\) weißt, kannst du auf verschiedene Weisen argumentieren.

Ich nehme das Lemma von Bezout mal als Anfangspunkt, da in der Aufgabe dadrüber eine solche Darstellung gefunden werden sollte.

Da wie oben ein gemeinsamer Teiler von \((a,b)\) (auch der größte) auch ein gemeinsamer Teiler von \((a,a+b)\) ist, muss \(\text{ggT}(a,b)\leq \text{ggT}(a,a+b)\). Der linke ggT ist ja ein gemeinsamer Teiler, käme also infrage, vielleicht gibt es ja aber einen noch größeren gemeinsamen Teiler von \((a,a+b)\).

Wir wissen also nach Bezout, dass \(\text{ggT}(a,b)=xa+yb\) für \(x,y\in\mathbb{Z}\) und dass der \(\text{ggT}\) die kleinste natürliche Zahl mit einer solchen Darstellung ist. Jetzt stellen wir das aber um zu:

\(\text{ggT}(a,b)=(x-y)a+y(a+b)\). Wir haben jetzt also so eine "Bezout-Darstellung" von \(\text{ggT}(a,b)\) bezüglich \((a,a+b)\) gefunden. Da deren \(\text{ggT}\) die kleinste natürliche Zahl mit dieser Eigenschaft ist, muss gelten: \(\text{ggT}(a,b)\geq \text{ggT}(a,a+b)\), und jetzt haben wir beide Richtungen der Gleichheit gezeigt.

Das ganze ließe sich auf viele verschiedene Weisen zeigen, aber dafür muss man eigentlich wissen, was ihr schon hattet und was nicht. Wenn du den euklidischen Algorithmus kennst, ist die Aussage ganz klar (einfach einen Schritt ausführen), aber im Korrektheitsbeweis ebendieses wird die zu zeigende Aussage normalerweise verwendet. Andererseits kann man das ganze auch "per Hand" über Teilbarkeitsgewurschtel machen, wie in deinem Ansatz. Aber beim ggT immer das Lemma von Bezout im Kopf zu haben, gibt dir sehr oft eine etwas elegantere Möglichkeit, zum Ziel zu gelangen.

Answer 2

Hier ist ein schneller, einfacher Weg.

Zeige einfach, dass die Teilermengen gleich sind:

\(d\:|\: a,b \Leftrightarrow d\:| a, (a+b)\)

\(\Rightarrow\):

Trivial. Nimm deinen Ansatz \(a=dx,\, b=dy\)

\(\Leftarrow\):

Fast genauso trivial. Nimm wieder deinen Ansatz mit \(a+b=dz,\, b=dy\) und nutze

\(b= (a+b) -a\)

Schlussfolgerung:
Wenn die Teilermengen gleich sind, müssen auch die größten gemeinsamen Teiler gleich sein.

Fertig.