Fibonaccizahl Nr. n. Beweis einer Primalität

Question

Es sei F(n) die n-te Fibonaccizahl und p≠5.

Beweise oder widerlege die Behauptung: p ist genau dann Primzahl, wenn mod(F(p-1),p)+mod(F(p+1),p)=1.

Answer 1

Schnell mal per Iterationsrechner getestet:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm#round(@P@Q5)*0.5+0.5,x)/@Q5)+@P@Q5)*0.5-0.5,x)*sin(PI*(x-0.5))/@Q5))@Ni=0;@N@Bi]=Fx(i-1)%25i+Fx(i+1)%25i;@Ci]=IsPrim(i);aD[i]=((@Bi]==1)&&@Ci])@O((@Bi]!=1)&&%20!@Ci]);@Ni%3E66@N0@N0@N#

bis 66 stimmt es.

Beweise hierfür kann man aus

http://www.ijon.de/mathe/fibonacci/node3.html

erstellen.

Comments

@hyper6: Es kann sein, dass man den Beweis über den Text zu angegebenem Link findet. Ich habe bisher noch nicht genügend lange darüber nachgedacht. Aber vorab schon mal Dank für diesen Link.

---

Wie im LINK in der Tabelle 2.2.11 zu sehen, gilt das nur bis 2 mod 5!

Also habe ich noch Pseudo-Primzahlen untersucht:

(fibonacci(5777+1) mod 5777)+(fibonacci(5777-1) mod 5777) =1

ABER 5777 = 53*109 -> das reicht als Gegenbeweis!!!

Wenn Wolfram richtig rechnet:

https://www.wolframalpha.com/input/?i=(fibonacci(5777%2B1)+mod+5777)%2B(fibonacci(5777-1)+mod+5777)

auch (fibonacci(4181+1) mod 4181)+(fibonacci(4181-1) mod 4181) =1, ABER 4181=37×113

also schon 2 Beispiele zur Widerlegung der Bahauptung.

Weitere: https://oeis.org/A212424

---

Es ist (richtige Rechnung vorausgesetzt) ein Gegenbeweis für eine Beweisrichtung. Die Sache gilt offenbar nicht nur für Primzahlen. Daher ist "genau dann, wenn" falsch. Ich werde das nochmal nachrechnen, aber schon mal vielen Dank.

---

Mehr dazu unter

https://en.wikipedia.org/wiki/Frobenius_pseudoprime

---

Vielen Dank auf für diesen Link. Ich habe auch noch die unmittelbaren Nachbarn von 5777 überprüft. Auch für 4181 und für 6721 gelingt dein Gegenbeweis. Damit ist eine Richtung des Satzes mehrmals widerlegt und meine Frage beantwortet.

---

Auch ich möchte mich für die interessante Frage bedanken, da:

- indirekte Antwort zu

https://www.mathelounge.de/193509/suche-steigende-zahlenfolgen-2000-keine-nachfolger-haben

(hier eine Folge, die Primzahlen bis 4177 generieren kann, dann aber plötzlich ungültig wird)

- ich bei der Recherche auch noch Fehler bei A000230(673) gefunden habe

---

Das ist aus meiner Sicht die längste Folge, die zunächst Primzahlen generiert und dann erst versagt. Solche "Rekorde" finde ich spannend.

---

Dann wird Dich auch die Frage

https://www.mathelounge.de/286534/javas-biginteger-nextprobableprime-keine-echte-primzahl

interessieren.

(die von Java ist übrigens besser als die von c# !)

So wie es aussieht, funktioniert diese Funktion auch noch mit Zahlen um 8000stellig!

Mehrere JAVA Programmierer (ich auch ) suchen schon über 5 Jahre und alle vermuten, dass erst ab 10000 Stellen erste falsche Ergebnisse herauskommen!

Erstaunlich ist die hohe Geschwindigkeit, die selbst bis 2000 stelligen Zahlen bei wenigen Sekunden bleibt.

---

Danke für die hochinteressanten Hinweise. Ich benutze ein veraltetes CAS mit dem Namen DERIVE. Damit lässt sich manches erst nach langer Wartezeit machen. JAVA beherrsche ich leider nicht.