Primzahlen der Form 2n2 - 1 finden

Question

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

Comments

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.Dann gilt: M_p = 2^p–1 ist genau dann eine Primzahl, wenn S(p–1) durch M_p 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.