ggt < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe 1 | Seien m, n [mm] \in \IN.
[/mm]
a) zu zeigen: ggt (m,n) = ggt (m, n-m)
b) Sei r>0 der Rest, der bei Division mit Rest von n durch m entsteht. Dann gilt: ggt (m,n)= ggt (m,r) |
| Aufgabe 2 | a) [mm] a,b\in \IZ \setminus [/mm] {0} => ggt a,b)= max({t| t ist Teiler von a und b}).
b) [mm] a,b\in \IN [/mm] => ggt (a,b) [mm] \le [/mm] ggt (a+b, a-b)
|
Hallo zusammen,
ich stehe hier vor einigen Problemen. Hier die Probleme im Detail:
zu 1.a): mir fehlt ein konkrter Ansatz
zu 1.b): ich hab gezeigt, dass [mm] T(m)\cap [/mm] T(n) = [mm] T(m)\cap [/mm] T(r) ist. Wie bekomme ich jetzt den ggt?
zu 2 a): [mm] ggt\le [/mm] max hab ich, mir fehlt max [mm] \le [/mm] ggt
zu 2 b): hier weiß ich gar nicht, wie ich anfangen soll.
Es wäre echt super, wenn mir jemand helfen könnte. Ein oder zwei Tipps wären schon hilfreich. Vielen Dank, der KommissarLachs
PS: Ich habe diese Fragen in keinem anderen Forum gestellt.
|
|
| |
|
Hallo KommissarLachs!
Hier schon mal was zur ersten Aufgabe:
> 1. Seien m, n [mm]\in \IN.[/mm]
> a) zu zeigen: ggt (m,n) = ggt (m,
> n-m)
> b) Sei r>0 der Rest, der bei Division mit Rest von n durch
> m entsteht. Dann gilt: ggt (m,n)= ggt (m,r)
a) Die Idee ist, zu zeigen, daß [mm]ggT (m,n) | ggT (m, n-m)[/mm] und [mm]ggT (m,n-m) | ggT (m, n)[/mm]. Dann müssen beide ggTs übereinstimmen.
b) ObdA sei [mm]n \ge m[/mm] (sonst vertausche einfach mit der Regel [mm]ggT(a,b) = ggT(b,a)[/mm]). Man kann n dann schreiben als [mm]n = km+r[/mm] mit geeignetem [mm]k,r \in \IZ[/mm] bzw. sogar [mm]k,r \in \IN[/mm]. Durch k-maliges Anwenden von a) erhält man:
[mm]ggT (m,n) = ggT (m, km+r) = ggT (m, (k-1)m+r) = ... = ggT (m, r)[/mm]
LG
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:16 Sa 12.05.2007 | | Autor: | MicMuc |
Aufgabe 1 solltest Du wohl elementar lösen, d.h. es wäre hilfreich, wie Ihr
ggt(n,m) für n,m [mm] $\in$ [/mm] N definiert habt.
[Deine Anmerkung lassen übrigens darauf schliessen, dass ihr den Schnitt der Teilermengen betrachtet und dort höchstwahrscheinlich die größte Zahl nehmt ... ???]
Karstens-Ansatz benutzt die Definition
ggT(n,m) = d , so gilt:
Jeder Teiler von n und m teilt d.
(Die Definition hat den Vorteil, dass sie auch in anderen [bestimmten] Ringen Sinn ergibt.
Nachteil: d ist dann aber nur bis auf die Multiplikation mit Einheiten des Ringes eindeutig ...)
Es gibt übrigens auch Definitionen die mit den Gruppen $Z / [mm] Z_{n}$ [/mm] und $z / [mm] Z_{m}$ [/mm] bzw. mit der Guppe, die von n und m erzeugt wird arbeiten ...
|
|
|
| |
|
Zur Aufgabe 2b)
> b) [mm]a,b\in \IN[/mm] => ggt (a,b) [mm]\le[/mm] ggt (a+b, a-b)
genügt m.E. folgendes:
Sei t=ggT(a,b), dann gilt t|a und t|b. Damit hat man unmittelbar t|(a+b) und t|(a-b) Somit ist
t [mm] \in [/mm] {s| s ist Teiler von (a+b) und (a-b)}
Ist r = ggT(a+b,a-b), so gilt nach a):
r = max({s| s ist Teiler von (a+b) und (a-b)}) [mm] \ge [/mm] t.
|
|
|
| |
|
So, nun noch was zur 2a)
> a) [mm]a,b\in \IZ \setminus[/mm] {0} => ggt a,b)= max({t| t ist
> Teiler von a und b}).
Vorweg: Der ggT zweier Zahlen ist immer eine positive ganze Zahl.
Sei [mm]d = ggT(a,b)[/mm] und T=max({t| t ist Teiler von a und b}). Klar ist [mm]d \in T[/mm]. Nach dem Lemma von Bézout gibt es ganze Zahlen r und s mit [mm]d = ggT(a,b) = ra + sb[/mm]. Ist e nun ein anderer Teiler aus T, so gilt e | a und e | b. Offenbar gilt dann auch [mm]e | ra+sb[/mm] und daher e|d. Dann muß aber e [mm] \le [/mm] d sein.
HTH
Karsten
|
|
|
|
