Fermatscher Primzahltest ohne Fermatsche Pseudoprimzahlen?

DIE PRIMZAHLENSERIE

Beitrag 25

Vermutung: Es gibt Funktionen, die keine Fermatschen Pseudoprimzahlen erzeugen. Dies bedeutet, daß alle Zahlen solch einer Funktion mit einem bestandenen Fermatschen Primzahltest nicht das Ergebnis ‚eventuell prim‘ haben, sondern das Ergebnis lautet bei einem bestandenen Fermatschen Primzahltest ‚prim‘.

Der Fermatsche Primzahltest wird durchgeführt mit:

$a^{p-1} \equiv 1 \mod{p}$

Es sei $k \in \mathbb{N}$ und $k \ge 0$ .

Folgende Funktionen $p_{pot}(k)$ liefern sowohl Primzahlen als auch zusammengesetzte Zahlen und im Fermatschen Primzahltest auch Fermatsche Pseudoprimzahlen:

$2k+3$

$4k+3$

$4k+5$

$6k+5$

$6k+7$

Um Fermatsche Pseudoprimzahlen zu vermeiden, darf keine zusammengesetzte Zahl einer zu definierenden Funktion den Fermatschen Primzahltest bestehen.

Ein Beispiel für eine Funktion, die vermutlich keine Fermatschen Pseudoprimzahlen hervorbringt, ist

$p_{pot} = 4k^2 + 12k + 7$

Ich habe von $k=0$ bis $k=10^9$ mit der Basis a=2 getestet und keine Fermatsche Pseudoprimzahl gefunden. In den Bereichen von $k=0$ bis $k=10^7$ habe ich mit den Basen 3, 4, 5 und 7 getestet und ebenfalls keine Fermatsche Pseudoprimzahl gefunden.

Desweiteren habe ich stichprobenartig Werte bis k=10^10000 getestet ohne daß Fermatsche Pseudoprimzahlen auftraten.

Ein weiteres Beispiel ist die Eulersche Funktion

$p_{pot} = k^2 + k + 41$

Ich habe von $k=0$ bis $k=10^9$ mit der Basis a=2 getestet und keine Fermatsche Pseudoprimzahl gefunden.

München, 16. Mai 2024

Gottfried Färberböck

Sprache:

Sprache:

DIE PRIMZAHLENSERIE

Fermatscher Primzahltest ohne Fermatsche Pseudoprimzahlen?