Zum Inhalt springen

Pseudoprimzahlen: Potenzen und Modulo

Aus Wikibooks


Potenzen

[Bearbeiten]

Wenn man eine Zahl immer wieder mit sich selbst multipliziert, erhält man eine Potenz. Eine bekannte Folge von steigenden Potenzen ist die folgende Folge aus Zweierpotenzen:

Verallgemeinert sieht eine solche Folge für eine beliebige Basis so aus:

Ein Feld solcher Zahlen sieht so aus:

n 1 2 3 4 5 6 7 8 9 ...
a
1 1 1 1 1 1 1 1 1 1 ...
2 2 4 8 16 32 64 128 256 512 ...
3 3 9 27 81 243 729 2187 6561 19683 ...
4 4 16 64 256 1024 4096 16384 65536 262144 ...
5 5 25 125 625 3125 15625 78125 390625 1953125 ...
6 6 36 216 1296 7776 46656 279936 1679616 10077696 ...
7 7 49 343 2401 16807 117649 823543 5764801 40353607 ...
8 8 64 512 4096 32768 262144 2097152 16777216 134217728 ...
9 9 81 729 6561 59049 531441 4782969 43046721 387420489 ...
10 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 ...
11 11 121 1331 14641 161051 1771561 19487171 214358881 2357947691 ...
12 12 144 1728 20736 248832 2985984 35831808 429981696 5159780352 ...
.. .. ... ... ... ... ... ... ... ... ...

Die Struktur, die dahinter steckt, wird sichtbar, wenn man das ganze Feld eine mithilfe von Modulo und einem festen Faktor unterzieht:

  • Beispiel: Modulo 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
2: 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
3: 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
4: 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
5: 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
6: 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
7: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
8: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
9: 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
10: 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
11: 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
12: 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
13: 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
14: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
15: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
16: 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
17: 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
18: 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
19: 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
20: 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
21: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

Die kleinste Einheit wird durch zwei Größen festgelegt, nämlich einmal den Wert , zu dem man das Ganze Modulo nimmt und der die Einheit nach unten begrenzt, und andererseits die Carmichael-Funktion , die der kleinste gemeinsame Faktor darstellt, zu der für jeden zu teilerfremden Wert gilt: .

Muster

[Bearbeiten]

Zu jeder natürlichen Zahl gibt es ein individuelles Erscheinungsbild. Andererseits haben bestimmte Arten von Zahlen Gemeinsamkeiten. Um das, was Zahlen gemeinsam haben, geht es hier:

natürliche Zahlen

[Bearbeiten]

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

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X X X X X
X: X X X X X X
X: X X X X X X
X: X X X X X X
A: A 1 A 1 A 1

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 steht. Dies ist also keine Charakteristik, die für Primzahlen typisch ist.

Primzahlen

[Bearbeiten]

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

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X 1 X X 1
X: X X A X X 1
X: X X 1 X X 1
X: X X A X X 1
A: A 1 A 1 A 1

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

Erstens die geschlossene Einserspalte
1 1 1 ...

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion zurückliefert.

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

1 A ...

Hier sind es die Werte, die die nach der nach Euler modifizierten Funktion zurückgeliefert werden.

Unterscheidung der Primzahlen in 4k-1 und 4k+1-Form

[Bearbeiten]

Die Struktur von Primzahlen der Form 4k-1 und 4k+1 unterscheidet sich in einer Spalte:

1 2 3 4 5 6 7 8 9 10
1: 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 5 10 9 7 3 6 1
3: 3 9 5 4 1 3 9 5 4 1
4: 4 5 9 3 1 4 5 9 3 1
5: 5 3 4 9 1 5 3 4 9 1
6: 6 3 7 9 10 5 8 4 2 1
7: 7 5 2 3 10 4 6 9 8 1
8: 8 9 6 4 10 3 2 5 7 1
9: 9 4 3 5 1 9 4 3 5 1
10: 10 1 10 1 10 1 10 1 10 1
1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1
Primzahl der Form 4k+3 Primzahl der Form 4k+1

Wie man sehen kann, ist die violette Spalte bei Primzahlen der Form 4k+1 symmetrisch und bei Primzahlen der Form 4k+3 komplementär.

Abgrenzung der Primzahlen von anderen natürlichen Zahlen

[Bearbeiten]

Bei allen anderen Arten natürlicher Zahlen fehlt die Geschlossenheit der beiden senkrechten Spalten.

1 2 3 4 5 6
1: 1 1 1 1 1 1
2: 2 4 8 7 5 1
3: 3 0 0 0 0 0
4: 4 7 1 4 7 1
5: 5 7 8 4 2 1
6: 6 0 0 0 0 0
7: 7 4 1 7 4 1
8: 8 1 8 1 8 1
1 2 3 4
1: 1 1 1 1
2: 2 4 8 1
3: 3 9 2 6
4: 4 1 4 1
5: 5 10 5 10
6: 6 6 6 6
7: 7 4 13 1
8: 8 4 2 1
9: 9 6 9 6
10: 10 10 10 10
11: 11 1 11 1
12: 12 9 3 6
13: 13 4 7 1
14: 14 1 14 1
Neun Fünfzehn

Wie man bei der Neun sehen kann, ist der Mittelbalken noch, wenn auch unterbrochen, vorhanden. Bei der 15 fehlt er vollständig.

Carmichael-Zahlen

[Bearbeiten]

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: muß durch 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.

1 2 3 4 5 6
1: 1 1 1 1 1 1
2: 2 4 8 7 5 1
3: 3 0 0 0 0 0
4: 4 7 1 4 7 1
5: 5 7 8 4 2 1
6: 6 0 0 0 0 0
7: 7 4 1 7 4 1
8: 8 1 8 1 8 1

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:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X 1 X X 1
X: X X A X X 1
X: X X 1 X X 1
X: X X A X X 1
A: A 1 A 1 A 1

Pseudoprimzahlen

[Bearbeiten]

Selbstreferenzierende Spalte

[Bearbeiten]

Wie ja schon bekannt ist, gilt für eine Primzahl , das für jede zu teilerfremde Basis gilt (Siehe blaue Spalte in der unteren Tabelle).

1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1

Nun ist aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl das ist, sich also z.B. in und zerlegen läßt. Das bedeutet, wenn sich ein Exponent in zwei Faktoren uns zerlegen läßt, das gilt.

Beispiele:

1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1

pure eulersche Pseudoprimzahl

[Bearbeiten]

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1
3: 3 9 2 6 18 4 12 11 8 24 22 16 23 19 7 21 13 14 17 1
4: 4 16 14 6 24 21 9 11 19 1 4 16 14 6 24 21 9 11 19 1
5: 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6: 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1
7: 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1
8: 8 14 12 21 18 19 2 16 3 24 17 11 13 4 7 6 23 9 22 1
9: 9 6 4 11 24 16 19 21 14 1 9 6 4 11 24 16 19 21 14 1
10: 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11: 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1
12: 12 19 3 11 7 9 8 21 2 24 13 6 22 14 18 16 17 4 23 1
13: 13 19 22 11 18 9 17 21 23 24 12 6 3 14 7 16 8 4 2 1
14: 14 21 19 16 24 11 4 6 9 1 14 21 19 16 24 11 4 6 9 1
15: 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16: 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1
17: 17 14 13 21 7 19 23 16 22 24 8 11 12 4 18 6 2 9 3 1
18: 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1
19: 19 11 9 21 24 6 14 16 4 1 19 11 9 21 24 6 14 16 4 1
20: 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
21: 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1
22: 22 9 23 6 7 4 13 11 17 24 3 16 2 19 18 21 12 14 8 1
23: 23 4 17 16 18 14 22 6 13 24 2 21 8 9 7 11 3 19 12 1
24: 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1
1 2 3 4 5 6 7 8 9 10
1: 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 16 32 31 29 25 17 1
3: 3 9 27 15 12 3 9 27 15 12
4: 4 16 31 25 1 4 16 31 25 1
5: 5 25 26 31 23 16 14 4 20 1
6: 6 3 18 9 21 27 30 15 24 12
7: 7 16 13 25 10 4 28 31 19 1
8: 8 31 17 4 32 25 2 16 29 1
9: 9 15 3 27 12 9 15 3 27 12
10: 10 1 10 1 10 1 10 1 10 1
11: 11 22 11 22 11 22 11 22 11 22
12: 12 12 12 12 12 12 12 12 12 12
13: 13 4 19 16 10 31 7 25 28 1
14: 14 31 5 4 23 25 20 16 26 1
15: 15 27 9 3 12 15 27 9 3 12
16: 16 25 4 31 1 16 25 4 31 1
17: 17 25 29 31 32 16 8 4 2 1
18: 18 27 24 3 21 15 6 9 30 12
19: 19 31 28 4 10 25 13 16 7 1
20: 20 4 14 16 23 31 26 25 5 1
21: 21 12 21 12 21 12 21 12 21 12
22: 22 22 22 22 22 22 22 22 22 22
23: 23 1 23 1 23 1 23 1 23 1
24: 24 15 30 27 21 9 18 3 6 12
25: 25 31 16 4 1 25 31 16 4 1
26: 26 16 20 25 23 4 5 31 14 1
27: 27 3 15 9 12 27 3 15 9 12
28: 28 25 7 31 10 16 19 4 13 1
29: 29 16 2 25 32 4 17 31 8 1
30: 30 9 6 15 21 3 24 27 18 12
31: 31 4 25 16 1 31 4 25 16 1
32: 32 1 32 1 32 1 32 1 32 1

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.