ggT(a,b)=ggT(a-b,b) < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:46 Mo 21.10.2013 | | Autor: | Ellie123 |
Hallo,
ich habe gelesen, dass die Aussage ggT(a,b)=ggT(a-b, b) für zwei ganze Zahlen a, b immer gilt. Leider habe ich aber keinen Beweis dazu gefunden. Mich würde jetzt interessieren, wie man diese Aussage auf dem kürzesten Weg beweisen kann. Kann mir da jemand weiterhelfen bzw. einen Tipp geben? Das wäre supernett.
Viele Grüße und vielen Dank schon mal, Ellie.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:06 Mo 21.10.2013 | | Autor: | M.Rex |
Hallo
Der ggT zweier Zahlen a und b ist doch die größte Zahl k, die in beiden Teilermengen T(a) und T(b) vorkommt.
Also
[mm] ggT(a;b)=max\{k|k\in T(a)\wedge k\in T(b)\}
[/mm]
Also teilt dieses k sowohl a als auch b.
Es gibt also eindeutig festgelegte ganze Zahlen m und n, so dass m=ka und n=kb
Das bedeutet:
[mm] k=\frac{a}{m}=\frac{b}{n}
[/mm]
Also gilt auch:
[mm] $a\cdot n=b\cdot [/mm] m$
bzw
[mm] $\green{a=\frac{b\cdot m}{n}}$
[/mm]
Betrachten wir nun den ggT((a-b);b)
Hier findest du ein maximales k', das in T(a-b) und T(b) liegt.
Also gibt es m' und n' so, dass m'=k'a und n'=k'a
Also gilt auch [mm] $(a-b)\cdot n'=b\cdot [/mm] m'$
Kommst du damit schonmal weiter?
Marius
|
|
|
|
