Rekursion von Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:34 Mo 14.11.2011 | | Autor: | m0ppel |
| Aufgabe | Gegeben ist folgende Rekursion: [mm] p_n [/mm] = [mm] 2*p_{n-1} \pm [/mm] 1
Beispiel: 2,3=2*2-1,7=2*3+1, 13=2*7-1, [mm] \dots [/mm] oder 2, 3=2*2-1, 5=2*3-1, 11=2*5+1, 23=2*11+1
Zeige: Es gibt keine unendliche Folge von Primzahlen dieser Art, unabhängig von der Startzahl p. |
Halli Hallo,
Ich habe hier diese Aufgabe und habe nicht den blassesten Schimmer, wie ich hier rangehen muss.
Ich habe mir ein paar Rekursionen angeguckt, kann aber überhaupt keinen Ansatz finden.
Bitte, Bitte Bitte helft mir.
Gruß m0ppel
|
|
| |
|
Hallo m0ppel,
diese Aufgabe erscheint mir ungleich schwerer als die andere, die Du gestern eingestellt hast. Man kann die gegebene Aussage auf eine andere zurückführen, die m.E. zwar wahr ist, die ich aber dennoch auch nicht beweisen kann. Hier trotzdem mal eine Skizze der Idee - vielleicht kann sie ja jemand anders zu Ende bringen.
> Gegeben ist folgende Rekursion: [mm]p_n[/mm] = [mm]2*p_{n-1} \pm[/mm] 1
> Beispiel: 2,3=2*2-1,7=2*3+1, 13=2*7-1, [mm]\dots[/mm] oder 2,
> 3=2*2-1, 5=2*3-1, 11=2*5+1, 23=2*11+1
> Zeige: Es gibt keine unendliche Folge von Primzahlen
> dieser Art, unabhängig von der Startzahl p.
>
> Ich habe hier diese Aufgabe und habe nicht den blassesten
> Schimmer, wie ich hier rangehen muss.
> Ich habe mir ein paar Rekursionen angeguckt, kann aber
> überhaupt keinen Ansatz finden.
Wenn man zeigen kann, dass jede Startzahl irgendwann auf einen zerlegbaren Wert führt, dann wäre der Beweis erbracht.
Nun kann man alle Rekursionen in zwei Klassen entsprechend der Startzahl einteilen:
1) Es ist [mm] p\equiv 1\mod{3}.
[/mm]
2) Es ist [mm] p\equiv -1\mod{3}.
[/mm]
Die einzige Primzahl, die in keine der beiden Restklassen fällt, ist die 3. Deren mögliche Folgeglieder sind aber 5 und 7, und die passen wieder in die beiden o.g. Klassen.
Nun stellt man fest, dass für [mm] p\equiv 1\mod{3} [/mm] nur die Rekursionsregel [mm] p_{n+1}=2p_n-1 [/mm] möglich ist, da sonst [mm] p_{n+1} [/mm] durch 3 teilbar wäre. Entsprechend geht für [mm] p\equiv -1\mod{3} [/mm] nur die Rekursionsregel [mm] p_{n+1}=2p_n+1.
[/mm]
Weiter kann man modulo einer Primzahl q in der Rekursionsfolge immer eine Zahl [mm] \equiv 0\mod{q} [/mm] erzeugt, wenn folgende zwei Bedingungen erfüllt sind.
Für Klasse 1, also [mm] p\equiv 1\mod{3}:
[/mm]
a) [mm] p\not\equiv 1\mod{q}
[/mm]
Für Klasse 2, also [mm] p\equiv -1\mod{3}:
[/mm]
a) [mm] p\not\equiv -1\mod{q}
[/mm]
und für beide Klassen:
b) [mm] ord_2(q)=q-1
[/mm]
(und irgendwie nehme ich an, dass Ihr Ordnungen noch gar nicht hattet, oder?)
Wenn man nun beweisen kann, dass es unendlich viele Primzahlen q gibt, die die Bedingung b erfüllen - die Ordnung von 2 in der multiplikativen Gruppe [mm] (\IZ/\q\IZ),\star [/mm] also q-1 ist, dann wäre die Aufgabe bewiesen, da die Startzahl p nicht 1 modulo unendlich vieler Primzahlen q sein kann, ohne selbst unendlich groß zu sein, was ein Widerspruch zur Annahme eines endlichen p wäre.
Leider ist das nicht so leicht zu zeigen, oder ich sehs nur nicht.
Die Schritte oben sind wie gesagt nur eine Skizze und hier nicht ausgeführt. Mir erscheint der Weg aber zu schwierig; Deine Aufgaben sprechen sonst eher für eine Vorlesung zur Einführung in die Zahlentheorie - da kann man nach ein paar Wochen ja noch nicht alles mögliche voraussetzen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:50 Di 15.11.2011 | | Autor: | felixf |
Moin rev,
> und für beide Klassen:
> b) [mm]ord_2(q)=q-1[/mm]
>
> (und irgendwie nehme ich an, dass Ihr Ordnungen noch gar
> nicht hattet, oder?)
>
> Wenn man nun beweisen kann, dass es unendlich viele
> Primzahlen q gibt, die die Bedingung b erfüllen - die
> Ordnung von 2 in der multiplikativen Gruppe
> [mm](\IZ/\q\IZ),\star[/mm] also q-1 ist,
das ist (im Wesentlichen) ein Spezialfall einer ![[]](/images/popup.gif) Vermutung von Artin, die sich bisher jeglichem Beweisversuch erfolgreich wiedersetzt hat.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:53 Di 15.11.2011 | | Autor: | reverend |
Hallo Felix,
> > Wenn man nun beweisen kann, dass es unendlich viele
> > Primzahlen q gibt, die die Bedingung b erfüllen - die
> > Ordnung von 2 in der multiplikativen Gruppe
> > [mm](\IZ/\q\IZ),\star[/mm] also q-1 ist,
>
> das ist (im Wesentlichen) ein Spezialfall einer
> Vermutung von Artin,
> die sich bisher jeglichem Beweisversuch erfolgreich
> wiedersetzt hat.
Dann darf man wohl annehmen, dass ein solcher Beweis nicht von Studenten in einer Übungsaufgabe verlangt wird...
Es macht die Aufgabe nicht weniger hartnäckig, finde ich.
lg
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:21 Di 15.11.2011 | | Autor: | m0ppel |
Lieber rev,
vielen Dank nochmal, für deine Mühe. Das scheint ja doch recht schwierig zu sein :O Wir werden sie heute Abend besprechen, ich bin schon sehr gespannt, was unser Prof dazu sagt.
Gruß
m0ppel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:21 Di 15.11.2011 | | Autor: | reverend |
Hallo m0ppel,
lies mal den unteren Teil des Threads, v.a. die Beiträge von Schadowmaster und donquijote.
Es bleibt dann festzuhalten: [mm] p_1|p_{p_1}
[/mm]
Damit ist die Aufgabe gelöst, nur liegt die Lösung hier nirgends "am Stück" vor und verlangt noch etwas Eigenarbeit.
Die überlassen wir aber Dir. Melde Dich, wenn etwas nicht klappt.
Grüße
reverend
|
|
|
| |
|
moin m0ppel,
Mit dem was reverend geschrieben hat nehmen wir mal an es sei $p [mm] \equiv [/mm] -1$ (mod 3).
Dann definieren wir eine Folge:
[mm] $a_0 [/mm] = p$
[mm] $a_1 [/mm] = 2p + 1$
[mm] $a_2 [/mm] = [mm] 2a_1 [/mm] +1 = 2*2p + 2*1 + 1$
[mm] $\cdots$
[/mm]
[mm] $a_n [/mm] = [mm] 2^n*p [/mm] + [mm] 2^{n-1} [/mm] + [mm] 2^{n-2} [/mm] + [mm] \cdots [/mm] + [mm] 2^0$
[/mm]
Wir haben also für alle $n [mm] \in \IN$ [/mm] den Wert:
[mm] $2^n*p [/mm] + [mm] \summe_{k=0}^{n-1} 2^k$
[/mm]
noch die hintere geometrische Summe auflösen, ein wenig umklammern, so steht da:
[mm] $2^n(p+1)-1$
[/mm]
Es bleibt noch zu zeigen:
Es gibt kein $p [mm] \in \IP$, [/mm] sodass für alle $n [mm] \in \IN$ [/mm] obiger Ausdruck in [mm] $\IP$ [/mm] liegt, oder anders: Zu jedem $p [mm] \in \IP$ [/mm] gibt es ein $n [mm] \in \IN$, [/mm] sodass [mm] $2^n(p+1)-1$ [/mm] keine Primzahl ist.
Mit dem kleinen Satz von Fermat dürftest du es schaffen zu jedem p ein solches n zu finden.
http://de.wikipedia.org/wiki/Kleiner_fermatscher_Satz
Der andere Fall (siehe dafür wieder reverends Post) dürfte recht ähnlich laufen.
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:36 Di 15.11.2011 | | Autor: | reverend |
Moin Schadow,
das ist eine übersichtliche Vereinfachung.
> [mm]2^n(p+1)-1[/mm]
>
> Es bleibt noch zu zeigen:
> Es gibt kein [mm]p \in \IP[/mm], sodass für alle [mm]n \in \IN[/mm] obiger
> Ausdruck in [mm]\IP[/mm] liegt, oder anders: Zu jedem [mm]p \in \IP[/mm] gibt
> es ein [mm]n \in \IN[/mm], sodass [mm]2^n(p+1)-1[/mm] keine Primzahl ist.
>
> Mit dem kleinen Satz von Fermat dürftest du es schaffen zu
> jedem p ein solches n zu finden.
Ohne probieren? Ich sehe noch nicht, wie man allgemein zeigen kann, dass zu jedem p ein solches n überhaupt existiert.
Hast Du eine Idee dazu?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:44 Di 15.11.2011 | | Autor: | donquijote |
> Moin Schadow,
>
> das ist eine übersichtliche Vereinfachung.
>
> > [mm]2^n(p+1)-1[/mm]
betrachte das ganze modulo p ...
> >
> > Es bleibt noch zu zeigen:
> > Es gibt kein [mm]p \in \IP[/mm], sodass für alle [mm]n \in \IN[/mm]
> obiger
> > Ausdruck in [mm]\IP[/mm] liegt, oder anders: Zu jedem [mm]p \in \IP[/mm] gibt
> > es ein [mm]n \in \IN[/mm], sodass [mm]2^n(p+1)-1[/mm] keine Primzahl ist.
> >
> > Mit dem
> kleinen Satz von Fermat
> dürftest du es schaffen zu
> > jedem p ein solches n zu finden.
>
> Ohne probieren? Ich sehe noch nicht, wie man allgemein
> zeigen kann, dass zu jedem p ein solches n überhaupt
> existiert.
> Hast Du eine Idee dazu?
>
> Grüße
> reverend
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:52 Di 15.11.2011 | | Autor: | reverend |
Hallo donquijote,
> > das ist eine übersichtliche Vereinfachung.
> >
> > > [mm]2^n(p+1)-1[/mm]
>
> betrachte das ganze modulo p ...
Ah. Oh. Manchmal liegt das Gute doch so nah, nur max. p-1 Schritte entfernt...
Grüße
reverend
|
|
|
|
