Der n-Primzahltest

DIE PRIMZAHLENSERIE

Beitrag 7

Der n-Primzahltest

Dieser Primzahltest ist kein Wahrscheinlichkeitstest, sondern ein indirekter Test, der eindeutig bestimmt, ob eine gewählte ungerade Zahl größer 1 eine Primzahl ist oder nicht.

Er basiert auf der Definition 6 aus Beitrag 1, Primzahldefinitionen:

Da es unendlich viele Primzahlen gibt und nur eine gerade Primzahl, nämlich 2, muß es unendlich viele ungerade Primzahlen geben. Daher folgende Definition für alle Primzahlen größer 2:

Eine Primzahl größer 2 ist eine ungerade Zahl U größer 2, die durch keine ungerade Zahl u im Bereich

$3 \leq u \le \sqrt{U}$

ohne Rest teilbar ist.

Daher werden für diesen Test nur ungerade Zahlen > 1 verwendet.

Mit

$U=2n+3$ ᴧ n ∈ ℕ

sind alle ungeraden Zahlen > 1 gegeben, die für diesen Test ausgewählt werden können.

Aufgelöst nach n ergibt sich

$n=\frac{U-3}{2}$

Das ermittelte n wird dann in die folgende Testfunktion t(n) eingesetzt:

$t(n)=\prod\limits_{k=0} ^{k_{max}} \lceil1-\frac{k+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3)}{n}\rceil$

mit

$k_{max}=\lfloor{\frac{|\sqrt{2n+3}-3|} {2}\rfloor}$

wobei n ∈ ℕ und n ≥ 1 sowie k ∈ ℕ und k ≥ 0.

Legende:

$\prod\limits_{k=0} ^{k_{max}}$ Produkt, in dem die Laufvariable k von 0 bis k_maxläuft

|x| Absolutwert von einem beliebigem Wert x

⌊x⌋ untere Gaußklammer, x abgerundet auf die nächste ganze Zahl

⌈x⌉ obere Gaußklammer, x aufgerundet auf die nächste ganze Zahl

Für ein gewähltes n>0 aus der Menge der natürlichen Zahlen ist t(n) entweder 0 oder 1.

Ist t(n)=0, dann ist 2n+3 für das gewählte n nicht prim.

Ist t(n)=1, dann ist 2n+3 für das gewählte n prim.

Beweis:

In Beitrag 6 wurde bewiesen, daß die Formel

n_km= 2k²+6k+3+m(2k+3) ʌ k, m ∈ ℕ

diejenigen n liefert, die in der Formel 2n+3 alle zusammengesetzten, ungeraden Zahlen größer 2 ergeben.

Bestimmt man nun alle n_km, die in der Nähe von einem gewählten n liegen, läßt sich feststellen, ob es ein n_kmgibt, für das gilt:

n = n_km

oder ob es kein n_kmgibt, das dem n gleich ist, also:

n ≠ n_km

Um dies deterministisch festzustellen, ist es erforderlich, alle n_kmvon k=0 bis k_max zu ermitteln. Für die Größe m reicht es, wenn nur das m_maxin Abhängigkeit von k im Bereich von 0 bis k_max verwendet wird. Die Größe m_max ist das m, das für das jeweilige k im Bereich von 0 bis k_max, den n_km-Wert bestimmt, der dem gewählten n in Abhängigkeit von k am nächsten und im Extremfall sogar gleich kommt.

Doch wie groß sind die Werte k_max und m_max?

Zunächst zu k_max:

Gemäß Definition 6, Beitrag 1 gilt:

Eine Primzahl größer 2 ist eine ungerade Zahl U größer 2, die durch keine ungerade Zahl u im Bereich

$3 \le u \le \sqrt{U}$

ohne Rest teilbar ist.

Setzt man

$U=2n+3$ ᴧ n ∈ ℕ

und

$u=2k+3$ ᴧ k ∈ ℕ

$u \le \sqrt{U}$

ergibt dies

$2k+3 \le \sqrt{2n+3}$

Die Lösungen für k bei einem gewählten n reichen von k=0 bis k=k_max für n, k ∈ ℕ.

Da wir k_maxalso als natürliche Zahl bestimmen wollen, aber bei der Auflösung nach k für k in den reellen Zahlenbereich kommen, schreiben wir zur besseren Unterscheidung:

$2k_{max_{r}}+3 = \sqrt{2n+3}$

Aufgelöst nach $k_{max_{r}}$ ergibt sich folgende Lösung:

$k_{max_{r}} = \frac{\sqrt{2n+3}-3}{2}$

Die reelle Lösung für $k_{max_{r}}$ kann durch Auf- oder Abrunden wieder in den Bereich der natürlichen Zahlen zurückgeführt werden.

In unserem Fall ist gemäß Definition 6 aus Beitrag 1 abzurunden.

Außerdem soll

$n_{km} \le n$

sein. Der Grund hierfür ist, daß die Funktion

$\frac{n-n_{km}}{n} \ge 0$

sein soll.

Und dies muß auch der Fall sein für

$\frac{n-n_{km_{max}}}{n} \ge 0$

Dadurch brauchen für den Test nicht mehr alle m in n_kmverwendet werden, sondern nur noch m_max in Abhängigkeit von k.

Da k und damit auch k_max ≥ 0 sein muß und k_max

für n=1 und n=2 negativ wäre, wird

$\sqrt{2n+3}-3$

als Absolutwert berechnet.

Somit ergibt sich für k_max

$k_{max}=\lfloor{\frac{|\sqrt{2n+3}-3|} {2}\rfloor}$

Der Term

$\lceil\frac{n-n_{km_{max}}}{n}\rceil$

kann nur die Werte 0 oder 1 annehmen, wenn

$n=n_{km_{max}}$ → $\lceil\frac{n_{km_{max}}-n_{km_{max}}}{n}\rceil=0$

$n>n_{km_{max}}$ → $\lceil\frac{n-n_{km_{max}}}{n}\rceil=1$

$n<n_{km_{max}}$ wird wie folgt ausgeschlossen:

Ersetzt man in der Formel

n_km= 2k²+6k+3+m(2k+3) ʌ k, m ∈ ℕ

n_km durch ein beliebiges n ∈ ℕ und bleibt k im natürlichen Zahlenbereich wird m zur reellen Zahl $m_{max_{r}}$

Auflöst nach $m_{max_{r}}$ , ergibt sich

$m_{max_{r}}=\frac{n-(2k^2+6k+3)}{2k+3}$

Da die Lösung für m_max ganzzahlig sein muß und $n_{km_{max}} \le n$ sein soll, ist $m_{max_{r}}$ abzurunden. Somit erhalten wir

$m_{max}=\lfloor\frac{n-(2k^2+6k+3)}{2k+3}\rfloor$

Eingesetzt in die Formel für n_km, ergibt

$n_{km_{max}}=2k^2+6k+3+\lfloor\frac{n-(2k^2+6k+3)}{2k+3}\rfloor(2k+3)$

Dies wiederum eingesetzt in

$\lceil\frac{n-n_{km_{max}}}{n}\rceil$

ergibt

$\lceil\frac{n-(2k^2+6k+3+\lfloor\frac{n-(2k^2+6k+3)}{2k+3}\rfloor(2k+3))}{n}\rceil$

Dieser Term kann nur die Werte 0 oder 1 annehmen, da $n_{km_{max}} \leq n$ ist.

Ist dieser Term 0, ergibt das gewählte n in der Formel 2n+3 keine Primzahl, sondern eine zusammengesetzte, ungerade Zahl.

Ist dieser Term 1, kann das gewählte n in der Formel 2n+3 eine Primzahl ergeben, muß aber nicht.

Bildet man aber das Produkt für alle k von 0 bis k_max und ist dieses Produkt nicht 0, sondern 1, dann ist mit diesem deterministischen Primzahltest eindeutig sichergestellt, daß 2n+3 eine Primzahl ist. Ist aber in diesem Produkt mindestens ein Faktor 0, dann ist das gesamte Produkt 0, und es ist mit diesem deterministischen Primzahltest eindeutig sichergestellt, daß 2n+3 für das gewählte n keine Primzahl ergibt.

Der Term

$\lceil\frac{n-(2k^2+6k+3+\lfloor\frac{n-(2k^2+6k+3)}{2k+3}\rfloor(2k+3))}{n}\rceil$

läßt sich umformen mit

$6k=5k+k$

$\lceil\frac{n-(2k^2+6k+3+\lfloor\frac{n-(2k^2+5k+3+k))}{2k+3}\rfloor(2k+3))}{n}\rceil$

und mit

$\frac{2k^2+5k+3}{2k+3}=k+1}$

$\lceil\frac{n-(2k^2+6k+3+\lfloor\frac{n-k}{2k+3}-k-1\rfloor(2k+3))}{n}\rceil$

und weiter in

$\lceil\frac{n-(2k^2+6k+3+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3)-\lfloor(k+1)\rfloor(2k+3))}{n}\rceil$

Da k+1 immer eine ganze Zahl ist, erübrigt sich das Abrunden.

Somit ergibt sich

$\lceil\frac{n-(2k^2+6k+3+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3)-(k+1)(2k+3))}{n}\rceil$

und weiter

$\lceil\frac{n-(2k^2+6k+3+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3)-(2k^2+5k+3))}{n}\rceil$

und weiter

$\lceil\frac{n-(k+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3)}{n}\rceil$

Dies läßt sich umformen in

$\lceil1-\frac{k+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3))}{n}\rceil$

Nun ist es aber erforderlich, daß das Produkt für alle k von 0 bis k_max gebildet wird, damit dieser Primzahltest deterministisch und damit eindeutig ist. Dies ist der Fall, wenn

$t(n)=\prod\limits_{k=0} ^{k_{max}} \lceil1-\frac{(k+\lfloor\frac{n-k}{2k+3}\rfloor(2k+3))}{n}\rceil$

mit

$k_{max}=\lfloor{\frac{|\sqrt{2n+3}-3|} {2}\rfloor}$

Was zu beweisen war.

Beispiele:

n=1 → t(1)=1 → 2*1+3=5 → prim

n=10 → t(10)=1 → 2*10+3=23 → prim

n=97 → t(97)=1 → 2*97+3=197 → prim

n=1001 → t(1001)=0 → 2*1001+3=2005 → nicht prim

n=30997 → t(30997)=0 → 2*30997+3=61997=13*19*251 → nicht prim

n=30103 → t(30103)=1 → 2*30103+3=60209 → prim

Die folgende Tabelle zeigt die Ergebnisse von n=1 bis n=20:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	1	0	1	1	0	1	1	0	1	0	0	1	1	0	0	1	0	1	1

Folgende Tabelle zeigt die Ergebnisse von n=1470 bis n=1480:

1470	1471	1472	1473	1474	1475	1476	1477	1478	1479	1480
0	0	0	0	0	1	0	1	0	0	1

München, 24. Oktober 2022

Gottfried Färberböck

Sprache:

Sprache:

DIE PRIMZAHLENSERIE

Der n-Primzahltest