ggT(a,b)=ggT(a,r) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Seien a,b natürliche Zahlen und a < b. Sei zudem r der Rest in b = a*q + r
Zeige, dass ggT(a,b) = ggT(a,r) |
Hallo.
Ich wäre so vorgegangen:
(1) Es ist ggT(a,b) = ggT(a, b-a)
Wegen b = a*q + r weiterhin:
ggT(a, b-a)=ggT(a, b-a-a)=...
Führe ich diesen Schritt insgesamt q-mal aus, dann erhalte ich
ggT(a,b) = ... = ggT(a, b-q*a) = ggT(a,r).
[ denn b - q*a = a*q+r - q*a = r ]
Damit wäre die Behauptung gezeigt, wenn ich das richtig gemacht habe.
(2) Nun müsste ich noch zeigen, dass ggT(a,b) = ggT(a, b-a) gilt, also für b>a.
Wie mache ich das? =/
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:56 Di 18.03.2014 | | Autor: | hippias |
> Seien a,b natürliche Zahlen und a < b. Sei zudem r der
> Rest in b = a*q + r
>
> Zeige, dass ggT(a,b) = ggT(a,r)
> Hallo.
>
> Ich wäre so vorgegangen:
>
> (1) Es ist ggT(a,b) = ggT(a, b-a)
>
> Wegen b = a*q + r weiterhin:
>
> ggT(a, b-a)=ggT(a, b-a-a)=...
>
> Führe ich diesen Schritt insgesamt q-mal aus, dann erhalte
> ich
Sauber wird es mit Induktion.
>
> ggT(a,b) = ... = ggT(a, b-q*a) = ggT(a,r).
> [ denn b - q*a = a*q+r - q*a = r ]
>
> Damit wäre die Behauptung gezeigt, wenn ich das richtig
> gemacht habe.
>
> (2) Nun müsste ich noch zeigen, dass ggT(a,b) = ggT(a,
> b-a) gilt, also für b>a.
>
> Wie mache ich das? =/
Zeige mittels der Definition der Teilbarkeit, dass wenn $d$ ein gemeinsamer Teiler von $a$ und $b$ ist, dass dann $d$ ein gemeinsamer Teiler von $a$ und $b-a$ ist und umgekehrt.
|
|
|
|
