Somos-4-Folge < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | (1) [mm] a_n a_{n-4} [/mm] = [mm] a_{n-1} a_{n-3} [/mm] + [mm] a_{n-2}^2, a_0 [/mm] = [mm] a_1 [/mm] = [mm] a_2 [/mm] = [mm] a_3 [/mm] = 1
Im Mathematical Intelligencer Vol. 13, No. 1, 1991, Seite 41 wird die ganzzahligkeit der Folge wie folgt bewiesen.
"First note because of (1) every four consecutive terms of the sequence are pairwise relatively prime. For suppose this is true up to [mm] a_n. [/mm] Then [mm] a_n [/mm] would have a prime factor p in common with [mm] a_{n-1} [/mm] or [mm] a_{n-3} [/mm] if and only if p also divided [mm] a_{n-2}, [/mm] contrary to the induction hypothesis.
We now show inductively that if [mm] a_{n-4}, \ldots, a_{n}, \ldots, a_{n+3} [/mm] are integers (clearly true for n=4), then is [mm] a_{n+4}, [/mm] and hence all [mm] a_{i}. [/mm] Writing [mm] a_{n-3} [/mm] = a, [mm] a_{n-2} [/mm] = b, [mm] a_{n-1} [/mm] = c we have [mm] a_na_{n-4} [/mm] = [mm] ac+b^2, [/mm] so [mm] a_{n} [/mm] divides [mm] ac+b^2. [/mm] By the preceding paragraph we may apply (1) to the sequence modulo [mm] a_n [/mm] giving
[mm] a,b,c,0,\frac{c^2}{a},\frac{c^3}{ab},\frac{c^3}{a^2}, a_n a_{n+4} \equiv \frac{c^5}{a^3 b^2}(ac+b^2) \equiv [/mm] 0,
so [mm] a_n [/mm] divides [mm] a_n a_{n+4}." [/mm] |
Hallo liebe Community,
ich muss diesen Beweis nachvollziehen und bekomme es irgendwie nicht ganz auf die Reihe. Ich hoffe ihr könnt mir dabei helfen.
Zunächst mal zum ersten Abschnitt. Also ich denke der Part ist einläuchtend. Wir haben also gezeigt, dass alle 4 aufeinanderfolgenden Glieder der Folge paarweise teilerfremd sind. Allerdings ist mir nicht ganz klar, wieso wir das brauchen. Aber vielleicht erst mal zum zweiten Part.
Also auch hier wieder das Prinzip der vollständigen Induktion. Für n=4 sind die ersten Folgeglieder 1, 1, 1, 1, 2, 3, 7 und 23. Also passt schon mal der Induktionsanfang. Außerdem wissen wir aus [mm] a_na_{n-4} [/mm] = [mm] ac+b^2, [/mm] dass [mm] a_n [/mm] ein Teiler von [mm] ac+b^2 [/mm] ist, weil ja laut Voraussetzung [mm] a_{n-4} [/mm] eine ganze Zahl ist.
Jetzt kommt der part den ich nicht verstehe. Zum einen betrachten wir die Folge modulo [mm] a_n, [/mm] wenn ich das richtig verstehe. Wieso dürfen wir das nur wegen dem vorherigen part? Ich mein wieso können wir modulo [mm] a_n [/mm] nicht anwenden, wenn nicht alle 4 aufeinanderfolgenden Glieder paarweise teilerfremd sind?
Also betrachten wir
[mm] a_{n-3} [/mm] mod [mm] a_n [/mm] = a
[mm] a_{n-2} [/mm] mod [mm] a_n [/mm] = b
[mm] a_{n-1} [/mm] mod [mm] a_n [/mm] = c
[mm] a_n [/mm] mod [mm] a_n [/mm] = 0
Das ist noch einläuchtend. Weil die Folge ja streng monoton wachsend für n > 4 ist (ist zwar nicht gezeigt aber das lässt sich leicht machen) ist [mm] a_{n-3} [/mm] < [mm] a_n [/mm] und damit [mm] a_{n-3} \text{ mod } a_n [/mm] = a.
Jetzt wirds irgendwie komisch.
Aus der Bildungsvorschrift folgt
[mm] a_{n+1} a_{n-3} [/mm] = [mm] a_{n} a_{n-2} [/mm] + [mm] a_{n-1}^2
[/mm]
[mm] a_{n+1} [/mm] a = [mm] a_{n} [/mm] b + [mm] c^2
[/mm]
[mm] a_{n+1} [/mm] = [mm] a_n \frac{b}{a} [/mm] + [mm] \frac{c^2}{a}
[/mm]
Wenn wir jetzt modulo [mm] a_n [/mm] anwenden folgt
[mm] a_{n+1} [/mm] mod [mm] a_n [/mm] = [mm] \left( a_n \frac{b}{a} + \frac{c^2}{a} \right) \text{ mod } a_n
[/mm]
Und nach der Rechenregel von Modulo damit:
[mm] a_{n+1} [/mm] mod [mm] a_n [/mm] = [mm] \left( \left( a_n \frac{b}{a} \text{ mod } a_n \right) + \left( \frac{c^2}{a} \text{ mod } a_n \right) \right) \text{ mod } a_n
[/mm]
Nun gibts das Problem, dass ich diese Regel nur anwenden kann wenn [mm] \frac{b}{a} [/mm] eine ganze Zahl wäre. Blöd aber, dass wir das überhaupt nicht wissen. Angenommen dem wäre so, dann würde weiter gelten
[mm] a_{n+1} [/mm] mod [mm] a_n [/mm] = [mm] \left( 0 + \left( \frac{c^2}{a} \text{ mod } a_n \right) \right) \text{ mod } a_n.
[/mm]
Mit ein bisschen umherrechnen, kann ich zeigen dass [mm] \frac{b}{a} [/mm] < [mm] a_n [/mm] ist.
Aber wie gesagt, irgendwie kann das so nicht stimmen.
Bei den weiteren Folgegliedern läuft es ähnlich. Wenn ich das eiskalt so rechne, gehts natürlich auf aber das darf ich ja eigentlich gar nicht weil ich nicht weiß ob [mm] \frac{b}{a} [/mm] eine ganze zahl ist. Oder auch [mm] \frac{c^2}{a}...
[/mm]
Ich fürchte ich hab einfach was übersehen.
Ich hoffe ihr könnt mir helfen. Eigentlich wirkt es ziemlich easy.
Vielen Dank schon mal im Voraus und liebe Grüße
Highchiller
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:31 Do 16.10.2014 | | Autor: | Teufel |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hi!
Ok, also dass die 4 aufeinanderfolgenden Zahlen teilerfremd sind, benötigst du, damit du modulo a_n Zahlen invertieren kannst. Beispiel: du willst $3x\equiv7 \mod{11}$ lösen. Dazu musst du durch 3 teilen, aber das kannst du nicht wie in $\IR$ machen, weil wir hier in einem anderen Ring sind. Stattdessen musst du das Inverse von 3 suchen, was hier 4 wäre, da $3*4\equiv 12 \equiv 1 \mod{11}$. Also hast du $x\equiv4*7\equiv 28\equiv 6\mod{11}$.
Nun zu deiner Aufgabe: Betrachtet man die Folge modulo a_n, so erhältst du $a_{n-3}\equiv a,a_{n-2}\equiv b,a_{n-1}\equiv c,a_n\equiv 0$. Nun bestimmen wir den Rest von a_{n+1} modulo a_n.
Nach der Gleichung gilt a_{n+1}a_{n-3}=a_na_{n-2}+a_{n-1}^2. Diese Gleichung gilt über \IZ nach Induktionsvoraussetzung, damit meine ich, dass alle Zahlen ganzzahlig sind. Nun bringen wr die Gleichung nach \IZ/a_n\IZ (d.h. wir rechnen beide Seiten modulo a_n).
z.B. geht die Gleichung 3*4+7=19 über \IZ nach \IZ/5\IZ in die Gleichung $3*4+7\equiv 19\mod{5}$ über.
Bei deiner Aufgabe erhalten wir also $a_{n+1}a\equiv a_nb+c^2\equiv 0*b+c^2\equiv c^2 \mod{a_n}$. Weil $b=a_{n-2}$ und a_n teilerfremd sind, kannst du eine Inverse zu $a$ finden modulo $a_n$. Also erhältst du $a_{n+1}}\equiv c^2b^{-1}\mod{a_n}$. Wichtig ist hier, dass die Inverse im Ring \IZ/a_n\IZ genommen wird, nicht über \IR!!
Zu deiner anderen Frage: Auch wenn die Zahlen nicht teilerfremd sind, kannst du so vorgehen. Aber dann könntest du $a_{n+1}a\equiv c^2 \mod{a_n}$ nicht weiter umformen. z.B. kannst du die Gleichung $4x\equiv 7\mod{8}$ nicht lösen, weil $ggt(4,8)=2>1$ gilt (du kannst auch alle x durchprobieren und siehst, dass keines die Gleichung löst). Die Teilerfremdheit ist auch wichtig, damit diese Brüche, die du da siehst, existieren.
Ach ja, noch etwas. Dass die Folge monoton steigt, ist egal. Du betrachtest Gleichungen modulo a_n, aber wenn a_{n-3}=a über \IZ gilt, dann gilt auch $a_{n-3}\equiv a\mod{a_n}$. Ich würde ohne diesen Modulo-Operator rechnen, wie du es versuchst, ich glaube der verwirrt hier mehr, als er bringt.
Ist alles etwas klarer geworden? Ich glaube, wenn du noch nicht so viel mit Restklassen gerechnet hast, ist das sehr verwirrend.
|
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
In der Tat habe ich bisher nicht viel mit Restklassen gerechnet. Aber ich dennoch verstanden wie das funktioniert. Vielen Dank für die Hilfe. Eine Kleinigkeit vielleicht noch.
> Bei deiner Aufgabe erhalten wir also $a_{n+1}a\quiva_nb+c^2\equiv0*b+c^2=c^2 \mod{a_n}$. Weil $b=a_{n-2}$ und a_n teilerfremd sind, kannst du eine Inverse zu $a$ finden modulo $a_n$. Also erhältst du $a_{n+1}}\equiv c^2b^{-1}\mod{a_n}$. Wichtig ist hier, dass die Inverse im Ring \IZ/a_n\IZ genommen wird, nicht über \IR!!
Hier hast du dich sicherlich verschrieben und gemeint
$a_{n+1}a \equiv a_n b+c^2\equiv0*b+c^2 \equiv c^2 \mod{a_n}$
Denn wenn nicht bin ich mir plötzlich nicht mehr so sicher. Auch das letzte Gleichheitszeichen müsste eigentlich ein $\equiv$ sein, nehm ich an.
Liebe Grüße und vielen Dank für die Hilfe
Highchiller
PS: Ich sehe grade, dass du dich im Quelltext tatsächlich nur vertippt hast. Ich schreib den Beitrag dennoch für alle weiteren Leser und falls ich doch noch einen Fehler getätigt habe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:13 So 19.10.2014 | | Autor: | Teufel |
Hi!
Jo, war vertippt, sorry. Hab es auch oben nochmal korrigiert! Aber schön, wenn jetzt alles klar ist.:)
|
|
|
|
