natürliche Zahlen

Alle natürlichen Zahlen haben eine Gemeinsamkeit in ihrer Struktur:

In der obersten Zeile befinden sich immer Einsen und in der untersten Zeile befinden sich immer im Wechsel A und 1, wobei A für ${\displaystyle n-1\ }$ steht. Dies ist also keine Charakteristik, die für Primzahlen typisch ist.

Primzahlen

Die für eine Primzahl typische Struktur sieht so aus:

Zu der für jede natürliche Zahl typischen Zeilen kommen zwei Charaktaristika bei Primzahlen hinzu:

Erstens die geschlossene Einserspalte

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion ${\displaystyle a^{\lambda (n)}}$ zurückliefert.

Zweitens die, ebenfalls geschlossene, Zeile aus Einsern und Zahlen A die die Zahl (n-1) repräsentieren.

Hier sind es die Werte, die die nach der nach Euler modifizierten Funktion ${\displaystyle a^{\frac {\lambda (n)}{2}}}$ zurückgeliefert werden.

Carmichael-Zahlen

Nachdem was bisher geschrieben worden ist, müßte die Neun, und damit alle Quadrate einer Primzahl, eine perfekte Fast-Primzahl sein. Dem ist aber nicht so. Damit eine Nichtprimzahl eine gute Fast-Primzahl sein kann, muß eines zutreffen: ${\displaystyle n-1\ }$ muß durch ${\displaystyle \lambda (n)\ }$ teilbar sein. Nichtprimzahlen mit dieser Eigenschaft nennt man Carmichael-Zahlen.

Was stimmt nun also an der Neun nicht? Die Einser liegen auf der blauen und, mit den Achten, auf der violetten Spalte.

Sie müßten allerdings auf der grünen Spalte liegen, und zusammen mit Achten auf der cyanen Spalte. Da ist aber weder eine Eins, noch eine Acht vorhanden. Einsen auf der grünen Spalte sind typisch für fermatsche Pseudoprimzahlen, und Einsen, bzw. (n-1) auf der cyanen Spalte sind typisch für eulersche Pseudoprimzahlen.

Die weiter oben abgebildete 15 ist eine fermatsche Pseudoprimzahl zu den Basen 4 und 11.

Folgerichtig muß man die Struktur für eine typische Primzahl ergänzen:

Selbstreferenzierende Spalte

Wie ja schon bekannt ist, gilt für eine Primzahl ${\displaystyle p\ }$, das für jede zu ${\displaystyle p\ }$ teilerfremde Basis ${\displaystyle a\ }$ ${\displaystyle a^{p-1}\equiv 1\mod p}$ gilt (Siehe blaue Spalte in der unteren Tabelle).

Nun ist ${\displaystyle p-1\ }$ aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl ${\displaystyle p=13\ }$ das ${\displaystyle (p-1)=12=2\cdot 2\cdot 3}$ ist, sich also z.B. in ${\displaystyle 2\cdot 6}$ und ${\displaystyle 3\cdot 4}$ zerlegen läßt. Das bedeutet, wenn sich ein Exponent ${\displaystyle n\ }$ in zwei Faktoren ${\displaystyle r\ }$ uns ${\displaystyle s\ }$ zerlegen läßt, das ${\displaystyle (a^{r})^{s}=(a^{s})^{r}=a^{r\cdot s}=a^{n}}$ gilt.

Beispiele:

• ${\displaystyle (5^{3})^{4}=5^{3\cdot 4}=5^{12}}$
• ${\displaystyle (5^{2})^{6}=5^{2\cdot 6}=5^{12}}$

pure eulersche Pseudoprimzahl

Mit der puren eulerschen Pseudoprimzahl ist eine fermatsche Pseudoprimzahl gemeint, bei der jede Basis, zu der die Zahl eine fermatsche Pseuodoprimzahl ist, auch gilt, das die Zahl zu der gleichen Basis auch eine eulersche Pseudoprimzahl ist.

Es gibt auch fermatsche Pseudoprimzahlen, bei denen die Pseudoprimzahl keine eulersche Pseudoprimzahl ist. Zu diesen fermatschen Pseudoprimzahlen zählen u.a. die 45, 91 und 153.