ggT = 1 von benachb. Fibonacci < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Weisen Sie (z.B. mit Induktion) nach, dass für zwei aufeinanderfolgende Fibonacci-Zahlen [mm] $f_{n}, f_{n+1}$ [/mm] gilt: [mm] $ggT(f_{n}, f_{n+1}) [/mm] = 1$. |
Hallo!
Bei obenstehender Aufgabe habe ich so meine Probleme. Wahrscheinlich, weil ich nicht genau weiß, was ich zu zeigen habe. Wir haben den ggT so definiert:
Sei $R$ ein kommutativer Ring mit Eins. Seien $a,b [mm] \in [/mm] R$. Ein Element [mm] $d\in [/mm] R$ heißt größter gemeinsamer Teiler von $a$ und $b$, wenn gilt:
(1) d|a und d|b
(2) [mm] $\forall [/mm] t [mm] \in [/mm] R: t|a [mm] \mbox{ und } [/mm] t|b [mm] \Rightarrow [/mm] t|d$
(Für $R = [mm] \IZ$ [/mm] wird zusätzlich [mm] $d\in \IN$ [/mm] gefordert, ist hier glaub ich aber nicht so wichtig.)
Ich würde jetzt ja mit Induktion anfangen.
IA: n = 0 [mm] \Rightarrow $ggT(f_{0},f_{1}) [/mm] = ggT(0,1) = 1$
IS: $n [mm] \to [/mm] n+1$
IB: Gegeben ist nun [mm] $ggT(f_{n},f_{n+1}) [/mm] = 1$. Ich muss nun zeigen, dass [mm] $ggT(f_{n+1}, f_{n+2}) [/mm] = 1$ ist.
Weil [mm] $ggT(f_{n},f_{n+1}) [/mm] = 1$, ist ja nun praktisch
(1) [mm] 1|f_{n} [/mm] und [mm] 1|f_{n+1} [/mm] (was aber vermutlich ziemlich wertlos ist, weil 1|? sowieso immer gilt.)
(2) [mm] $\forall [/mm] t [mm] \in [/mm] R: [mm] t|f_{n} \mbox{ und } t|f_{n+1} \Rightarrow [/mm] t|1$ (Ich vermute, dass ich diese Bedingung verwenden muss)
Nun muss ist ja zeigen, dass daraus
(2) [mm] $\forall [/mm] t [mm] \in [/mm] R: [mm] t|f_{n+1} \mbox{ und } t|f_{n+2} \Rightarrow [/mm] t|1$ (Ich vermute, dass ich diese Bedingung verwenden muss)
folgt. Kann ich irgendwie aus dem oberen (2) sowas wie [mm] $t|f_{n} [/mm] + [mm] f_{n+2} \Rightarrow [/mm] t|1$ machen, damit ich das unten einsetzen kann?
Vielen Dank für Eure Hilfe,
Stefan.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:22 Mo 17.11.2008 | | Autor: | statler |
Hi Stefan!
Versuch mal zu zeigen (mit Induktion):
[mm] f_{n}*f_{n+2} [/mm] - [mm] f_{n+1}^{2} [/mm] = [mm] (-1)^{n+1}
[/mm]
Daraus folgt sofort die gewünschte Aussage.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:59 Mo 17.11.2008 | | Autor: | felixf |
Hallo
> Versuch mal zu zeigen (mit Induktion):
>
> [mm]f_{n}*f_{n+2}[/mm] - [mm]f_{n+1}^{2}[/mm] = [mm](-1)^{n+1}[/mm]
>
> Daraus folgt sofort die gewünschte Aussage.
Oder alternativ: benutze, dass $ggT(a, b) = ggT(a, b - a)$ ist, und verwende [mm] $f_{n+2} [/mm] = [mm] f_n [/mm] + [mm] f_{n+1}$.
[/mm]
LG Felix
|
|
|
| |
|
Hallo und danke für deine Antwort!
Ich habe im Vorlesungshefter nachgesehen und diese Beziehung haben wir noch nicht konkret gezeigt. Wir haben nur
$ggT(a*c,b*c) = ggT(a,b)*c$ (Dasselbe auch nochmal für Division)
...
Danach geht es nur noch ums kgV...
Kann man das schnell zeigen, dass $ggT(a,b) = ggT(a, b-a)$ (z.B. mit Euklidischem Algorithmus?)
Stefan.
|
|
|
| |
|
Hallo Stefan,
> Hallo und danke für deine Antwort!
>
> Ich habe im Vorlesungshefter nachgesehen und diese
> Beziehung haben wir noch nicht konkret gezeigt. Wir haben
> nur
>
> [mm]ggT(a*c,b*c) = ggT(a,b)*c[/mm] (Dasselbe auch nochmal für
> Division)
>
> ...
> Danach geht es nur noch ums kgV...
> Kann man das schnell zeigen, dass [mm]ggT(a,b) = ggT(a, b-a)[/mm]
> (z.B. mit Euklidischem Algorithmus?)
Das geht einfach(er) mit Rückgriff auf die Definition des ggt bzw. auf die elementare Teilbarkeitslehre.
Das hattet ihr aber bestimmt schon:
[mm] $(d\mid a\wedge d\mid b)\Rightarrow d\mid [/mm] (xa+yb)$ für alle [mm] $x,y\in\IZ$
[/mm]
Also insbesondere für $x=-1, y=1$
>
> Stefan.
>
LG
schachuzipus
|
|
|
| |
|
Hallo!
Danke für deine Antwort! Ich wäre soweit:
Was ich mit unseren Vorlesungsregeln "voraussetzen" kann, ist
$ggT(a,b)|a [mm] \mbox{ und } [/mm] ggT(a,b)|b [mm] \Rightarrow [/mm] ggT(a,b)|b-a$
Daraus müsste ich jetzt $ggT(a,b) = ggT(a,b-a)$ folgern - Mir ist das jetzt noch nicht ganz klar, wie ich das hinbekomme... Wir haben bis jetzt in Sachen nur Teilbarkeitslehre- und Regeln sowie die Definition von ggT gehabt, was ich effektiv benutzen könnte.
Vielen Dank für Eure Hilfe,
Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:56 Mo 17.11.2008 | | Autor: | felixf |
Hallo
> Danke für deine Antwort! Ich wäre soweit:
> Was ich mit unseren Vorlesungsregeln "voraussetzen" kann,
> ist
>
> [mm]ggT(a,b)|a \mbox{ und } ggT(a,b)|b \Rightarrow ggT(a,b)|b-a[/mm]
>
> Daraus müsste ich jetzt [mm]ggT(a,b) = ggT(a,b-a)[/mm] folgern - Mir
Nimm dir ein Ringelement $d$, und zeige, dass es genau dann $a$ und $b$ teilt, wenn es $a$ und $b - a$ teilt.
Daraus folgt $ggT(a, b) = ggT(a, b - a)$.
LG Felix
|
|
|
| |
|
Hallo und danke für deine Antwort!
> Nimm dir ein Ringelement [mm]d[/mm], und zeige, dass es genau dann [mm]a[/mm]
> und [mm]b[/mm] teilt, wenn es [mm]a[/mm] und [mm]b - a[/mm] teilt.
>
> Daraus folgt [mm]ggT(a, b) = ggT(a, b - a)[/mm].
Genau diesen Schritt verstehe ich nicht! Ich kann denk ich schnell die obige Forderung beweisen, aber ich weiß nicht warum dann [mm]ggT(a, b) = ggT(a, b - a)[/mm] gilt... Ich komm mir grad mal wieder ziemlich blöd vor. Rein vom euklidischen Algorithmus und logisch ist es mir natürlich klar, aber wie man das formal aufschreibt - denn solche eine Folgerung hatten wir nicht.
Kannst du mir nochmal helfen?
Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:24 Di 18.11.2008 | | Autor: | statler |
Guten Morgen Stefan!
> > Nimm dir ein Ringelement [mm]d[/mm], und zeige, dass es genau dann [mm]a[/mm]
> > und [mm]b[/mm] teilt, wenn es [mm]a[/mm] und [mm]b - a[/mm] teilt.
> >
> > Daraus folgt [mm]ggT(a, b) = ggT(a, b - a)[/mm].
>
> Genau diesen Schritt verstehe ich nicht!
In [mm] \IZ [/mm] betrachtest du einfach die Menge der gemeinsamen Teiler von a und b und die Menge der gemeinsamen Teiler von a und b-a und überlegst dir, daß sie gleich sind. Dann sind natürlich auch ihre beiden größten Elemente gleich.
In einem Hauptidealring zeigst du, daß das von a und b erzeugte Ideal gleich dem von a und b-a erzeugten Ideal ist. Dann sind die erzeugenden Elemente nicht unbedingt gleich, unterscheiden sich aber nur um eine Einheit. Der ggT ist ja auch nicht eindeutig bestimmt.
Gruß aus Harburg
Dieter
|
|
|
| |
|
Danke für deine Antwort!
Ich glaube jetzt hab ich's, kann das bitte noch mal jemand durchsehen:
Betrachte die Zahlen $a,\ b [mm] \in \IZ$. [/mm] Dann gibt es eine Menge
$A := [mm] \{ d\ \in \IZ\ |\ d|a$ und $d|b \}$
[/mm]
und eine Menge
$A' := [mm] \{ d \in \IZ\ |\ d|a$ und $d|(b-a) \}$
[/mm]
Nun gilt $A = A'$, weil einerseits
[mm] $d\in [/mm] A [mm] \Longleftrightarrow [/mm] d|a$ und $d|b [mm] \Rightarrow [/mm] d|a$ und $d|(b-a) [mm] \Rightarrow [/mm] d\ [mm] \in\ [/mm] A'$
(wegen eines tollen Satzes der Vorlesung)
und andererseits
[mm] $d\in [/mm] A' [mm] \Longleftrightarrow [/mm] d|a$ und $d|(b-a) [mm] \Rightarrow [/mm] d|a$ und $d|b [mm] \Rightarrow d\in [/mm] A$
(wegen eines tollen Satzes der Vorlesung).
Somit gilt $A = A'$.
Es ist $ggT(a,b) [mm] \in [/mm] A$, d.h. [mm] $\forall t\in [/mm] A$ gilt $t|ggT(a,b)$. Andererseits ist $ggT(a,b-a) [mm] \in [/mm] A'$ und somit [mm] $\forall t\in [/mm] A'$ gilt $t|ggT(a,b-a)$ Insgesamt ergibt sich
[mm] $\forall t\in [/mm] A: t|ggT(a,b) [mm] \mbox{ und } [/mm] t|ggT(a,b-a)$
woraus ????? folgt $ggT(a,b) = ggT(a,b-a)$. Das Problem ist, dass wir keine Ordnung in den Ringen gegeben haben und ich so nicht einfach sagen kann dass es ein "größtes" Element gibt...
(Induktion über die Fibonacci-Zahlen:)
IA klar.
IS: [mm] n\to [/mm] n+1
IV: [mm] $ggT(f_{n},f_{n+1}) [/mm] = 1$
IB:
[mm] $ggT(f_{n+1},f_{n+2}) \overset{Eig. Fibo}{=} ggT(f_{n+1},f_{n} [/mm] + [mm] f_{n+1}) \overset{Hilfssatz}{=} ggT(f_{n+1},(f_{n} [/mm] + [mm] f_{n+1}) [/mm] - [mm] f_{n+1}) [/mm] = [mm] ggT(f_{n+1},f_{n}) [/mm] = [mm] ggT(f_{n},f_{n+1}) \overset{IV}{=} [/mm] 1$.
q.e.d. 
Danke für Eure Hilfe,
Stefan!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:05 Mi 19.11.2008 | | Autor: | statler |
Guten Morgen!
> Ich glaube jetzt hab ich's, kann das bitte noch mal jemand
> durchsehen:
> Betrachte die Zahlen [mm]a,\ b \in \IZ[/mm]. Dann gibt es eine
> Menge
>
> [mm]A := \{ d\ \in \IZ\ |\ d|a[/mm] und [mm]d|b \}[/mm]
>
> und eine Menge
>
> [mm]A' := \{ d \in \IZ\ |\ d|a[/mm] und [mm]d|(b-a) \}[/mm]
>
> Nun gilt [mm]A = A'[/mm], weil einerseits
>
> [mm]d\in A \Longleftrightarrow d|a[/mm] und [mm]d|b \Rightarrow d|a[/mm] und
> [mm]d|(b-a) \Rightarrow d\ \in\ A'[/mm]
>
> (wegen eines tollen Satzes der Vorlesung)
>
> und andererseits
>
> [mm]d\in A' \Longleftrightarrow d|a[/mm] und [mm]d|(b-a) \Rightarrow d|a[/mm]
> und [mm]d|b \Rightarrow d\in A[/mm]
>
> (wegen eines tollen Satzes der Vorlesung).
>
> Somit gilt [mm]A = A'[/mm].
Jetzt hängt es ein bißchen davon ab, wie ihr den ggT definiert habt und was du über ihn weißt. Da A und A' die Mengen der gemeinsamen Teiler sind, ist klar, daß ihre jeweiligen größten Elemente übereinstimmen. Das kleine Büchlein von Scholz-Schoeneberg über Zahlentheorie braucht immerhin die ersten 20 Seiten, um sich da durchzufummeln.
> Es ist [mm]ggT(a,b) \in A[/mm], d.h. [mm]\forall t\in A[/mm]
> gilt [mm]t|ggT(a,b)[/mm]. Andererseits ist [mm]ggT(a,b-a) \in A'[/mm] und
> somit [mm]\forall t\in A'[/mm] gilt [mm]t|ggT(a,b-a)[/mm] Insgesamt ergibt
> sich
>
> [mm]\forall t\in A: t|ggT(a,b) \mbox{ und } t|ggT(a,b-a)[/mm]
>
> woraus ????? folgt [mm]ggT(a,b) = ggT(a,b-a)[/mm].
> Das Problem ist,
> dass wir keine Ordnung in den Ringen gegeben haben und ich
> so nicht einfach sagen kann dass es ein "größtes" Element
> gibt...
In einem Hauptidealring (HIR) ist ein ggT von a und b ein erzeugendes Element des von a und b erzeugten Ideals. Aber du hast oben schon mehr oder weniger gezeigt, daß a und b dasselbe Ideal erzeugen wie a und b-a (a = a und b = (b-a) + a).
> (Induktion über die Fibonacci-Zahlen:)
> IA klar.
> IS: [mm]n\to[/mm] n+1
> IV: [mm]ggT(f_{n},f_{n+1}) = 1[/mm]
> IB:
>
> [mm]ggT(f_{n+1},f_{n+2}) \overset{Eig. Fibo}{=} ggT(f_{n+1},f_{n} + f_{n+1}) \overset{Hilfssatz}{=} ggT(f_{n+1},(f_{n} + f_{n+1}) - f_{n+1}) = ggT(f_{n+1},f_{n}) = ggT(f_{n},f_{n+1}) \overset{IV}{=} 1[/mm].
>
> q.e.d.
Das sieht gut aus und war ja auch die ursprüngliche Aufgabe.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Hallo Dieter,
danke für deine Antwort. Ich denke ich habs verstanden
Stefan.
|
|
|
| |
|
Hallo und danke für deine Antwort!
> [mm]f_{n}*f_{n+2}[/mm] - [mm]f_{n+1}^{2}[/mm] = [mm](-1)^{n+1}[/mm]
>
> Daraus folgt sofort die gewünschte Aussage.
Wieso ergibt sich daraus die gewünschte Aussage [mm] $ggT(f_{n},f_{n+1}) [/mm] = 1$? Das ist mir noch nicht ganz klar
Ist das so weil ich jetzt praktisch [mm] $a,b\in [/mm] R$ in Form von $a = [mm] f_{n+2}, [/mm] b = [mm] -f_{n+1}$ [/mm] gefunden habe sodass
$a * [mm] f_{n} [/mm] + [mm] b*f_{n+1} [/mm] = 1$
?
Kann dann, selbst wenn zwei Zahlen [mm] f_{n} [/mm] und [mm] f_{n+1} [/mm] die Gleichung erfüllen, es nicht trotzdem noch gemeinsame Teiler > 1 geben?
Danke für Eure Hilfe,
Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:44 Mo 17.11.2008 | | Autor: | statler |
> Hallo und danke für deine Antwort!
>
> > [mm]f_{n}*f_{n+2}[/mm] - [mm]f_{n+1}^{2}[/mm] = [mm](-1)^{n+1}[/mm]
> >
> > Daraus folgt sofort die gewünschte Aussage.
>
> Wieso ergibt sich daraus die gewünschte Aussage
> [mm]ggT(f_{n},f_{n+1}) = 1[/mm]? Das ist mir noch nicht ganz klar
>
> Ist das so weil ich jetzt praktisch [mm]a,b\in R[/mm] in Form von [mm]a = f_{n+2}, b = -f_{n+1}[/mm]
> gefunden habe sodass
>
> [mm]a * f_{n} + b*f_{n+1} = 1[/mm]
Genau: Ein gemeinsamer Teiler von [mm] f_n [/mm] und [mm] f_{n+1} [/mm] ist Teiler der linken Seite, also auch Teiler der rechten Seite. a und b sind übrigens nicht in [mm] \IR [/mm] (das würde nicht reichen), sondern in [mm] \IZ.
[/mm]
Gruß
Dieter
|
|
|
| |
|
Hallo!
Danke für deine Antwort. Das habe ich verstanden
Mit R meinte ich den Ring R 
Stefan.
|
|
|
|
