GGT beweise < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:09 Do 28.03.2013 | | Autor: | DieNase |
| Aufgabe 1 | Ubung ¨ 8. Seien m und n ganze Zahlen. Zeige: wenn ganze Zahlen a und b existieren mit
am + bn = 1, dann ist ggT(m, n) = 1. |
| Aufgabe 2 | Ubung ¨ 10. Sei Fn die Folge der Fibonacci-Zahlen, gegeben durch die Rekursion
F0 = F1 = 1 Fn+1 = Fn + Fn−1
Zeige, daß ggT(Fn, Fn+1) = 1 fur jedes ¨ n (Induktion). |
Zu eins muss ich sagen das ich da nicht wirklich weiß wie ich das zeigen soll... Ich hab mir überlegt ich könnte ja sagen der ggT(m,n) > 1 doch wie weiter? Hier steh ich total auf der leitung...
Bei den fibonachi zahlen hab ich 2 dinge bisher getan:
1.) eine art kete gebildet
[mm] F_{n+1} [/mm] = [mm] F_{n} [/mm] + [mm] F_{n-1}
[/mm]
[mm] F_{n+2} [/mm] = [mm] 2*F_{n} [/mm] + [mm] F_{n-1}
[/mm]
[mm] F_{n+5} [/mm] = [mm] 8*F_{n} [/mm] + [mm] 5*F_{n-1}
[/mm]
Jetzt müsste ich zeigen das die zahlen die vor Fn bzw. Fn-1 sind teilerfremd sind. (naja das sind die fibonachizahlen ^^)
Mein nächster anlauf war dann dieser hier:
[mm] ggT(F_{n},F_{n+1}) [/mm] = 1
Basis [mm] F_{0} [/mm] und [mm] F_{1} [/mm] ggT(1,1) = 1
[mm] ggT(F_{n+1},F_{n+2}) [/mm] = 1
beides anders geschrieben:
a * [mm] F_{n} [/mm] + b * [mm] F_{n+1} [/mm] = 1
d * [mm] F_{n} [/mm] + (c+d) * [mm] F_{n+1} [/mm] = 1 --> [mm] ggT(F_{n+1},F_{n+2}) [/mm] umgeschrieben.
mein ziel wars eigentlich die erste zeile irgendwie in der zweiten zeile zu finden. Naja irgendwie ist sie schon da. Aber halt auch net wirklich ganz. Ich dachte mir jetzt ok ich weiß das Fn und Fn+1 teiler fremd sind.
Argo muss ich nurnoch zeigen das d und c teilerfremd sind und ich wäre fertig.
Und irgendwie hab ich das gefühl das ich zweimal das selbe problem bloß anders formuliert habe.
Mein lösungsansatz war dieser hier:
d = e*q +0
c = e*p +0
Sollte also d und c ein teiler haben so muss dies ja gelten. Doch so recht kann ich damit immernoch nix anfangen.
Anhang(e ist meine angenommener teiler der existiert wollte das ganze durch widerspruch zeigen)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
.
> Zu eins muss ich sagen das ich da nicht wirklich weiß wie
> ich das zeigen soll... Ich hab mir überlegt ich könnte ja
> sagen der ggT(m,n) > 1 doch wie weiter? Hier steh ich total
> auf der leitung...
Der Ansatz ist gut. Zeige damit, dass es keine a,b geben kann mit an+bm=1, da n und m einen gemeinsamen nicht-trivialen Teiler haben.
> Bei den fibonachi (sic) zahlen hab ich 2 dinge bisher getan:
Ich würde hier Aufgabe 1 nicht verwenden.
Zeige ggT(a,a+b)=ggT(a,b) für beliebige a,b.
Dann ist die Induktion ein Zweizeiler
|
|
|
|
