+1 Daumen
1,7k Aufrufe


wie findet man effizient Primzahlen der Form 2n^2 - 1? Welche n muss man nicht überprüfen etc.? Das einzige, was ich rausfinden konnte, war, dass $$2n^2 - 1 \equiv 1 ( mod 3 )$$ oder $$2n^2 - 1 \equiv -1 ( mod 3 )$$, was mir aber nicht sehr weiterhilft.


Bin für jeden Tipp dankbar!

Danke,

Thilo
Avatar von 4,3 k
Kannst du nicht folgendermassen umformen?  ( modulo -Schreibweise dazudenken)

2n^2 - 1 = 1             
2n^2 -2 = 0

2(n^2 -1) = 0

(n-1)(n+1) = 0
Ja stimmt. Aber wüsste nicht, wie mir das dabei weiterhelfen kann, einige n auszuschließen.

Inzwischen habe ich eine kleine Verbesserung gefunden: Wenn 7 | n-2, dann 7 | 2*n^2 - 1, weil

$$a_n = 7 + 4\cdot ( \frac{(n-2)(n-1)}{2} ) + 6(n-2)$$

Dabei sind das in der Mitte die Dreieckszahlen 1+2+3+...+n-2.

Also kann ich n ausschließen, für die $$n \equiv 2 ( mod 7 )$$ gilt ( ausser für n = 2 )
Vielleicht hilft auch noch die rekursive Folge für 2n^2 - 1 weiter:

$$a_0 := 7$$

$$a_{n+1} = a_n + 4n + 6$$

Die Differenz zweier Folgenglieder ist also immer 4n + 6
Auch die $$n\equiv 5 \mod 7$$ liefern keine Primzahlen, ebenso $$n\equiv 3,14 \mod 17$$.
Danke, wie kommst du darauf? Interessiert mich blos, weil ich ja noch am lernen bin :P
Da 5=-2 mod 7 sind 2,5 die NST des reinquadratrischen Polynoms 2n²-1. Weitere Primzahlen p für welche 2n²-1 eine NST modulo p hat sind die in denen 1/2 eine Quadratzahl ist. Nach dem 2. Ergänzungssatz zum Reziprozitätsgesetz sind diese p von der Form +/-1 mod 8 . Ob sich das Suchen der entsprechenden NST für größere p noch lohnt weiß ich nicht.
Okay, danke :) Habe gerade etwas entdeckt, das scheint zu stimmen ( habe ich aber nicht ausführlich bewiesen ):

$$a_n = b \Rightarrow b | a_{ b \cdot k + n }$$ mit k natürlich oder 0.

Also wenn $$2n^2 - 1 = b \Rightarrow b | 2( b \cdot k + n )^2 - 1$$.

Z.B. mit $$a_2 = 2 \cdot 2^2 - 1 = 7$$ ist $$2\cdot( 7\cdot k + 2)^2 - 1$$ immer durch 7 teilbar, also nicht prim.


Wenns stimmt, kann ich damit sehr viele n ausschließen.
Klar: $$2n^2 - 1 | 2( (2n^2 - 1) \cdot k + n )^2 - 1 = (2n^2 - 1) \cdot ( 4k^2 n^2 -2k^2 + 4kn + 1 )$$
Okay, also mit den bisherigen Erkenntnissen kann ich in etwa die Hälfte aller Kandidaten im Voraus ausschließen. Also für 2 <= n <= 500000 kann man z.B. 240592 ausschließen. Die anderen n müsste man noch auf die Primzahleigenschaft überprüfen. Das ist leider noch nicht genug. Ich muss alle 2 <= n <= 50.000.000 überprüfen. Davon scheiden 24.092.132 Kandidaten aus. Die restlichen müsste ich noch übeprüfen, aber das dauert selbst bei schnellen Primzahltests noch ca. 5 Minuten und das ist mir zu lange :(

Habt ihr noch irgendwas, was man verwenden könnte? Vor allem etwas wie dass 2n^2 - 1 noch andere a_n teilt und die daher nicht prim sein können..

Danke

Hi,

Lucas Lehmer Test:

Sei p ungerade und prim. Die Folge S(k) sei definiert durch S(1) = 4, S(k+1) = S(k)2–2.Dann gilt: Mp = 2p–1 ist genau dann eine Primzahl, wenn S(p–1) durch Mp teilbar ist.
Wikipedia gucken und genaueres lesen ;-)

legendär
Und was hat das mit der Aufgabe zu tun?


Na er wollte doch wissen wie man das gut überprüft und welche n man übeprüfen muss.

Der Lukas-Lehmer Test ist ein Primzahltest für sog. Mersenne-zahlen, d.h. Zahlen der Form \( 2^n-1\). Es geht hier aber um Zahlen der Form 2n²-1. Auf die ist der Test nicht anwendbar.

Achso, stimmt natürlich... Antwort ist jetzt ein Kommentar.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community