Pseudoprimzahlen: Meta: Überblick

Vorwort

Was soll das Buch bezwecken?

Das Buch soll das zeigen, was jenseits der Primzahlen kommt. Die faszinierende Welt der Pseudoprimzahlen.

Warum dieses Buch?

In der deutschen Wikipedia sind einige interessante Artikel über den Bereich Pseudoprimzahlen, Primzahlen und Randbereiche entstanden. So die Artikel Carmichael-Zahl, Eulersche Pseudoprimzahl, Starke Pseudoprimzahl, Lucas-Folge u.s.w. . Nun ist die Wikipedia ja eine Enzyklopädie und kein Lehrbuch, was bedeutet, dass man weder in die Tiefe gehen kann, noch Zusammenhänge so vernetzen kann, wie man das gerne möchte.

Für wen ist dieses Buch gedacht?

Dieses Buch ist für jene gedacht, die gerne tüfteln. Der Stoff ist vielleicht nicht einfach zugänglich, aber wer eine gewisse Hürde übersprungen hat, für den eröffnen sich Welten (auch in Bezug auf die Primzahlen). Was dieses Buch nicht ist, ist ein Lehrbuch, das den Leser von Punkt zu Punkt führt. Der Leser muß sich seine Ziele selber suchen. Wer sich nicht schon für die natürlichen Zahlen, und insbesondere für Primzahlen interessiert, der wird mit diesem Lehrbuch wenig Freunde haben.

Ein rechenintensives Thema

Da bei den Pseudoprimzahlen, insbesondere denen, die unter das Schema fermatsche Pseudoprimzahlen fallen, oft große Potenzen auftauchen, kommt man, wenn man das in diesem Buch geschriebene nachvollziehen möchte, nicht darum herum, selbst Programme zu schreiben. Manches läßt sich auch "zu Fuß" oder mit dem Taschenrechner nachrechnen, aber ohne Computer kommt man letztlich nicht aus. In dem Buch ist auch ein Kapitel mit fertigen Quellcodes, aber man läßt sich möglicherweise etwas entgehen, wenn man sich nicht selbst Gedanken macht, und die Programme selbst schreibt. Aber das muß der Leser letztendlich selber wissen.

Unterscheidung

Wenn in dem Text über eine Zahl gesagt wird, sie sie eine Pseudoprimzahl, dann bedeutet das, dass diese Zahl zusammengesetzt ist, und sich in irgendeinem Kriterium wie eine Primzahl verhält. Genauso meint ein eine Zahl ist eine starke Pseudoprimzahl, das eine Basis existiert, zu der sich diese zusammengesetzte Zahl, aufgrund des Kriteriums für starke Pseudoprimzahlen, wie eine Primzahl verhält.

Ist dagegen von einer fpsp(n) die Rede, also einer fermatschen Pseudoprimzahl zu einer bestimmten Basis $n\$ , dann ist klar, dass man sich genau auf diese Basis $n\$ bezieht (abgesehen davon, dass diese fermatsche Pseudoprimzahl noch zu anderen Basen pseudoprim ist).

Pseudoprimzahlen

Was sind Pseudoprimzahlen

Schon seit der Antike (Euklid von Alexandria, ca. 3. Jahrhundert v.u.Z) beschäftigten sich Menschen mit Primzahlen.

Primzahlen, das sind natürliche Zahlen größer 1, die nur durch 1 und durch sich selber teilbar sind. So sind sie definiert.

Allerdings lassen sich damit größere Zahlen schlecht darauf prüfen, ob sie Primzzahlen sind. Wie unpraktisch diese Eigenschaft für den Primzahlentest ist, lässt sich daran ermessen, dass um eine Zahl der Größenordnung $\approx 10^{100}$ auf ihre Primalität zu testen, ihre Teilbarkeit von $\approx 10^{50}$ Zahlen getestet werden müßte.

Aber die Primzahlen haben noch viele andere Eigenschaften. Eigenschaften der Form: "Wenn $p\$ eine Primzahl ist, dann hat $p\$ die Eigenschaft $x\$

Um aus dem Buch Prime Numbers - A Computational Perspective 1 zu zitieren: "Wenn $p\$ eine Primzahl ist, dann ist $p\$ gleich 2, oder $p\$ ist eine ungerade Zahl". In dieser Richtung funkioniert die Definition. Allerdings läßt sie sich nicht umdrehen: "Wenn $p\$ gleich 2 oder eine ungerade Zahl ist, dann ist $p\$ eine Primzahl" ist ein ausgemachter Blödsinn. Es gibt weitere solcher "Wenn $p\$ eine Primzahl ist, dann hat $p\$ die Eigenschaft $x\$ ", die sinnvoller sind, deren Umdrehung aber ebenfalls falsche Schlüsse wären:

Wenn

p\

eine Primzahl ist,

dann hat $p\$ die Form $4n+1\$ beziehungsweise $4n-1\$
dann hat $p\$ die Form $6n+1\$ beziehungsweise $6n-1\$
dann teilt $p\$ jede Zahl der Form $a^{p}-a\$ mit $a\geq 2$
dann teilt $p\$ den Ausdruck $L_{p}-1\$ , wobei $L_{p}\$ das p.te Glied der Lucas-Folge ist.
dann teilt $p\$ das p.te Glied der Perrin-Folge

Falsche Primzahlen, die man aus der Umdrehung solcher "Wenn $p\$ eine Primzahl ist, dann hat $p\$ die Eigenschaft $x\$ "-Regeln bekommt, nennt man Pseudoprimzahlen. Das allerdings mit einer gewissen Einschränkung:

Zusammengesetze Zahlen, die den Formen

4n+1\

,

4n-1\

,

6n+1\

bzw.

6n-1\

entsprechen, werden deswegen noch lange nicht zwangsläufig als Pseudoprimzahlen bezeichnet. Dazu sind schon striktere Eigenschaften wie Beispielsweise

q\

teilt

a^{q}-a

oder

q\

teilt

P_{q}\

oder

q\

teilt

L_{q}-1\

nötig.

Solche Pseudoprimzahlen, die dem Satz $a^{p}\equiv a\mod p$ (kleine fermatsche Satz) genügen nennt man fermatsche Pseudoprimzahlen zur Basis $a\$ . Dies ist die bekannte und wichtigste Klasse der Pseudoprimzahlen.

Der umgekehrte Weg

Für eine Primzahl $n$ trifft, daß zu jeder natürlichen Zahl $a\$ der Satz $a^{n}\equiv a\mod n$ gilt. Das gleiche gilt auch für Carmichael-Zahlen. In sofern gleichen sich Primzahlen und Carmichael-Zahlen. Aber wenn man nicht den Satz $a^{n}\equiv a\mod n$ verwendet, sondern statt dessen $a^{n-1}\equiv 1\mod n$ , dann gibt es einen Unterschied. Für die Primzahlen gilt $a^{n-1}\equiv 1\mod n$ nur für $a\$ die teilerfremd zu $n\$ sind. Auch das gilt für Carmichael-Zahlen. Allerdings sind Carmichael-Zahlen, im Gegensatz zu Primzahlen, zusammengesetzt. Das bedeutet, dass bei Carmichael-Zahlen, im Gegensatz zu Primzahlen, der Bereich, zwischen $1\$ und $n\$ , an teilerfremden Zahlen $a\$ lückenhaft ist.

Es gibt jede Menge Pseudoprimzahlen, die noch lückenhafter sind, als die Carmichael-Zahlen. Die Basis stellt die fermatsche Pseudoprimzahl dar. Jede eulersche Pseudoprimzahl, jede starke Pseudoprimzahl und auch jede Carmichael-Zahl ist eine fermatsche Pseudoprimzahl. Wie findet man alle fermatschen Pseudoprimzahlen in einem vorgegebenen Bereich zwischen $3\$ und $n\$ ? Alle fermatschen Pseudoprimzahlen haben gemeinsam, daß es natürliche Zahlen $a\$ gibt, für die $a^{n-1}\equiv 1\mod n$ gilt, und gleichzeitig natürliche Zahlen $a\$ gibt, für die $a^{n-1}\equiv 1\mod n$ nicht gilt. Kann man den Bereich der natürliche Zahlen $a\$ einschränken? Es macht Sinn, den Bereich der natürliche Zahlen $a\$ auf $1\$ bis $n-1\$ einzuschränken, und zwar deswegen, weil sich daß Muster der Basen $a\$ wiederholt. Als Beispiel die fermatsche Pseudoprimzahl $15\$ :

15\

ist pseudoprim zu den Basen

4\

und

11\

. Aus der Regel: Wenn

n

pseudoprim zu

a\

ist, dann ist

n

auch pseudoprim zu allen

a+bn\

, also der Summe von

a\

mit dem vielfachen von

n

. Für

15\

sind das die Basen

19,26,31,41,49,56,...\

.

Es macht sogar Sinn, den Bereich noch weiter einzuschränken. Für jede natürliche Zahl gilt nämlich folgendes:

	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

Wie man sehen kann, trifft auf jede natürliche Zahl $n$ folgende zwei Sätze zu:

$(bn+1)^{n-1}\equiv 1\mod n$

und

$(bn-1)^{n-1}\equiv 1\mod n$

Da diese beiden Sätze auf jede natürliche Zahl $n\$ zutreffen, haben sie keine Aussagekraft, ob eine Zahl eine Primzahl oder eine Pseudoprimzahl ist. Demzufolge braucht man nur im Bereich zwischen $2\$ und $n-2\$ zu testen. Diese Einschränkung hat zur Folge, dass eine Reihe von Zahlen ( $4,6,8,9,...\$ ) als Kandidaten für fermatsche Pseudoprimzahlen herausfallen.

Diese Einschränkung des Bereiches von $2\$ und $n-2\$ zählt zwangsläufig auch für die eulerschen Pseudoprimzahlen, die starken Pseudoprimzahlen und alle anderen Arten von Pseudoprimzahlen, die auf der fermatschen Pseudoprimzahl basieren. Allerdings kann man diese Einschränkung bei den Carmichael-Zahlen ignorieren.

Pseudoprimzahlen

Die fermatsche Pseudoprimzahl im allgemeinen

Wie Ende des vorherigen Kapitels erwähnt ist, sind fermatsche Pseudoprimzahlen zusammengesetzte Zahlen $q\$ , für die gilt, daß $q\$ den Ausdruck $a^{q}-a$ teilt, wobei $a\$ größer, oder aber wenigstens gleich, 2 sein muß. Abgesehen von den Dreierpotenzen, also 3; 9; 27; 81; 243; 729; ... , sind alle ungeraden, zusammengesetzten Zahlen, fermatsche Pseudoprimzahlen. Bei den geraden, zusammengesetzen Zahlen sieht das noch ein wenig anders als. Dort gibt es mehr zusammengesetzte Zahlen, die keine Fermatschen Pseudoprimzahlen sind.

Ein paar Daten zu den fermatschen Pseudoprimzahlen

Zu jeder Basis $a\geq 2$ gibt es eine kleinste fermatsche Pseudoprimzahl. In der folgenden Tabelle sind die kleinsten Pseudoprimzahlen bis zur Basis 121 aufgeführt:

Die kleinste fermatsche Pseudoprimzahl zur Basis a
a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp
2:	341	22:	69	42:	205	62:	91	82:	91	102:	133
3:	91	23:	33	43:	77	63:	341	83:	105	103:	133
4:	15	24:	115	44:	65	64:	85	84:	415	104:	145
5:	124	25:	28	45:	76	65:	112	85:	129	105:	451
6:	35	26:	45	46:	133	66:	91	86:	145	106:	133
7:	25	27:	65	47:	65	67:	85	87:	91	107:	133
8:	21	28:	45	48:	91	68:	91	88:	91	108:	341
9:	28	29:	35	49:	66	69:	85	89:	99	109:	117
10:	33	30:	49	50:	119	70:	169	90:	623	110:	259
11:	15	31:	49	51:	65	71:	105	91:	115	111:	190
12:	65	32:	93	52:	85	72:	65	92:	105	112:	121
13:	21	33:	85	53:	65	73:	111	93:	301	113:	133
14:	39	34:	55	54:	265	74:	91	94:	121	114:	205
15:	341	35:	51	55:	63	75:	91	95:	141	115:	133
16:	51	36:	91	56:	95	76:	105	96:	133	116:	195
17:	45	37:	45	57:	65	77:	247	97:	105	117:	145
18:	25	38:	65	58:	133	78:	341	98:	153	118:	121
19:	45	39:	95	59:	87	79:	91	99:	145	119:	177
20:	57	40:	91	60:	341	80:	169	100:	153	120:	187
21:	55	41:	105	61:	91	81:	85	101:	175	121:	133

Wenn man nun alle Pseudoprimzahlen aus der Tabelle, unter der Weglassung der doppelten Pseudoprimzahlen auflistet, bekommt man folgende Folge:

 15,  21,  25,  28,  33,  35,  39,  45,  49,  51,  55,  57,  63,  65,  66,  69,  76,  77,  85,  87,  91,  93,  95,  99,
105, 111, 112, 115, 117, 119, 121, 124, 129, 133, 141, 145, 153, 169, 175, 177, 187, 190, 195, 205, 247, 259, 265, 301,
341, 415, 451, 623

Das sind 52 Zahlen. Zum Vergleich: Bis 10 existieren 4 Primzahlen, hier sind es 0 Pseudoprimzahlen; bis 100 sind es 25 Primzahlen, hier sind es 24 Pseudoprimzahlen; bis 1000 sind es 168 Primzahlen, hier sind es 52. Allerdings muß man zugestehen, das noch gar nicht alle Pseudoprimzahlen berücksichtigt werden konnten. Wie aber verhält sich die Verteilung der Pseudoprimzahlen nun wirklich? Gibt es innerhab bestimmter Grenzen mehr Pseudoprimzahlen als Primzahlen, oder verhält es sich umgekehrt?

Dabei muß man Unterscheiden. Meint man die fermatschen Pseudoprimzahlen zu einer bestimmten Basis $a\$ , so sind es, in definierten Grenzen, weniger Pseudoprimzahlen als Primzahlen:

Basis	Fermatsche Pseudoprimzahlen
2	341, 561, 645, 949, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, ...
3	91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, ...
4	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, ...
5	124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5611, 5662, 5731, 7449, 7813, 8029, ...
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, ...
7	25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, ...
8	21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, ...
9	28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, ...
10	33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, ...

Meint man dagegen die Menge aller fermatschen Pseudoprimzahlen, die zu irgendeiner Basis $a\geq 2$ pseudoprim ist, dann gibt es, in definierten Grenzen mehr Pseudoprimzahlen als Primzahlen:

  15    21    25    28    33    35    39    49    51    52    55    57    63    65    66    69    70    75
  76    77    85    87    91    93    95    99   105   111   112   115   117   119   121   123   124   125
 129   130   133   135   141   143   145   147   148   153   154   155   159   161   165   169   171   172
 175   176   177   183   185   186   187   189   190   195   196   201   203   205   207   208   209   213
 215   217   219   221   225   231   232   235   237   238   244   245   246   247   249   253   255   259
 261   265   267   268   273   275   276   279   280   285   286   287   289   291   292   295   297   299
 301   303   304   305   309   310   315   316   319   321   322   323   325   327   329   333   335   339
 341

Wenn man sich jetzt unterschiedliche fermatsche Pseudoprimzahlen anschaut

Die fermatsche Pseudoprimzahl

Eine zusammengesetzte Zahl $q\$ gilt dann als fermatsche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl $a\$ mit $\operatorname {ggT} (a,q)=1$ gibt, so dass für $a\$ und $q\$ gilt: $a^{q-1}\equiv 1\mod q$ .

Beispiel:

15=3\cdot 5

ist eine zusammengesetze Zahl

$4^{15-1}\$	$\equiv 1\mod 15$
$11^{15-1}\$	$\equiv 1\mod 15$

Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

Natürlich gibt es zu einer fermatschen Pseudoprimzahl $q\$ niemals nur eine Basis $a\$ , zu der $q\$ pseudoprim ist.

Das läßt sich an einer Pseudoprimzahl, sagen wir beispielsweise mal 21, zeigen:

Die 21 ist pseudoprim zur Basis 13 pseudoprim.

Wenn eine ungerade, fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ pseudoprim ist, so ist $q\$ auch zu der Basis $(q-a)\$ pseudoprim.

Da 21 pseudoprim zur 13 ist, ist 21 auch pseudoprim zu (21-13) = 8.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ pseudoprim ist, so ist $q\$ auch zu der Basis $a^{n}\$ mit einer natürlichen Zahl $n\geq 1\$ pseudoprim.

Da 21 pseudoprim zu 8 und 13 ist, ist 21 auch zu

8^{2}=64,\ 13^{2}=169,\ 8^{3}=512,\ 13^{3}=2197,\ ...\

pseudoprim.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis der Form $a^{n}\$ mit $n\geq 1\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu $a^{n}\mod q\$ mit $n\geq 1\$

Pseudoprimzahlen

Die fermatsche Pseudoprimzahl

Eine zusammengesetzte Zahl $q\$ gilt dann als fermatsche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl $a\$ mit $\operatorname {ggT} (a,q)=1$ und $2\leq a\leq q-2$ gibt, so das für $a\$ und $q\$ gilt: $a^{q-1}\equiv 1\mod q$ .

Beispiel:

15=3\cdot 5

ist eine zusammengesetze Zahl

$4^{15-1}\$	$\equiv 1\mod 15$
$11^{15-1}\$	$\equiv 1\mod 15$

Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

Natürlich gibt es zu einer fermatschen Pseudoprimzahl $q\$ niemals nur eine Basis $a\$ , zu der $q\$ pseudoprim ist.

Das läßt sich an einer Pseudoprimzahl, sagen wir beispielsweise mal 21, zeigen:

Die 21 ist pseudoprim zur Basis 13 pseudoprim.

Wenn eine ungerade, fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ mit $a<q\$ pseudoprim ist, so ist $q\$ auch zu der Basis $(q-a)\$ pseudoprim.

Da 21 pseudoprim zur 13 ist, ist 21 auch pseudoprim zu (21-13) = 8.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ mit $a<q\$ pseudoprim ist, so ist $q\$ auch zu der Basis $a^{n}\$ mit einer natürlichen Zahl $n\geq 1\$ pseudoprim.

Da 21 pseudoprim zu 8 und 13 ist, ist 21 auch zu

8^{2}=64,\ 13^{2}=169,\ 8^{3}=512,\ 13^{3}=2197,\ ...\

pseudoprim.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis der Form $a^{n}\$ mit $n\geq 1\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu $a^{n}\mod q\$ mit $n\geq 1\$

Pseudoprimzahlen

Eulersche Pseudoprimzahl

Eine zusammengesetzte Zahl n ist eine eulersche Pseudoprimzahl, wenn es wenigstens eine natürliche Zahl $a>1$ zur Basis hat, die teilerfremd zu n ist, und für die entweder gilt:

a^{\frac {n-1}{2}}\equiv 1{\pmod {n}}

oder

a^{\frac {n-1}{2}}\equiv -1{\pmod {n}}.

Eine solche Zahl nennt man auch eulersche Pseudoprimzahl zur Basis a, kurz: EPsP(a).

Ableitung der eulerschen Pseudoprimzahl aus der fermatschen Pseudoprimzahl

Ein Beispiel für eine eulersche Pseudoprimzahl zur

Es läßt sich ziemlich einfach, nämlich durch quadrieren, zeigen, das eine eulersche pseudoprimzahl auch eine fermatsche Pseudoprimzahl ist. Es sei n eine eulersche Pseudoprimzahl zur Basis a. Es gilt also:

a^{\frac {n-1}{2}}=\pm 1{\pmod {n}}.

Folglich ist:

a^{n-1}=\left(a^{\frac {n-1}{2}}\right)^{2}=(\pm 1)^{2}=1{\pmod {n}},

und deshalb ist n auch eine fermatsche Pseudoprimzahl zur Basis a.

Daraus das eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl ist, läßt sich nicht der Umkehrschluß ziehen, dass jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das läßt sich anhand der fermatschen Pseudoprimzahl 15 zeigen:

11^{7}\equiv 11{\pmod {15}}

.

Die Zahl 15 ist also keine eulersche Pseudoprimzahl zur Basis 11. Aber

{\left(11^{7}\right)}^{2}=11^{14}\equiv 1{\pmod {15}},

demzufolge ist 15 eine fermatsche Pseudoprimzahl zur Basis 11.

Pseudoprimzahlen

die starke Pseudoprimzahl

Um eine starke Pseudoprimzahl zu sein, muß eine zusammengesetzte Zahl $n=d\cdot 2^{s}+1\$ nur eine natürliche Zahl a zur Basis haben, für die entweder $a^{d}\equiv 1\mod n$ oder $a^{d\cdot 2^{r}}\equiv -1\mod n$ mit $0\leq r\leq (s-1)$ gilt.

Um zu zeigen, wie unterschiedlich starke Pseudoprimzahlen ausfallen können, werden als Beispiele die drei Zahlen 781, 1541 und 25 gezeigt. An der Zahl 781 zeigen wird erstmal die Zerlegung gezeigt:

Zerlegung

Gesucht wird das $d\$ zu einer Zahl $n\$ zu der Formel $n=d\cdot 2^{s}+1\$ . Die Formel können wir Umstellen:

$n=d\cdot 2^{s}+1$
$n-1=d\cdot 2^{s}$
${\frac {n-1}{2^{s}}}=d$

Am Beispiel der Zahl 781 sieht das so aus: Die Primfaktorzerlegung von $781-1=2^{2}\cdot 3\cdot 5\cdot 13\$ . Wenn man die 2er-Potenzen entfernt, bleibt für $n=781\$ das $d=3\cdot 5\cdot 13=195\$ übrig.

781 zur Basis 5

$n=781\ \ \ d=195\$

$5^{195}\equiv 1\mod 781$ also ist 781 eine starke Pseudoprimzahl zur Basis 5

1541 zur Basis 5

$n=1541\ \ \ d=385\$

$5^{385}\equiv 1540\mod 1541$ also ist 1541 eine starke Pseudoprimzahl zur Basis 5

25 zur Basis 7

$n=25\ \ \ d=3\$

$7^{3}\equiv 18\mod 25$

$7^{6}\equiv 24\mod 25$ also ist 25 eine starke Pseudoprimzahl zur Basis 7

305 zur Basis 11

Dies ist ein Gegenbeispiel.

$n=305\ \ \ d=19\$

$11^{19}\equiv 111\mod 305$

$11^{38}\equiv 121\mod 305$

$11^{76}\equiv 1\mod 305$

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11

starke Pseudoprimzahl und eulersche Pseudoprimzahl

Damit eine zusammengesetzte natürliche Zahl eine starke Pseudoprimzahl zur Basis $a\$ sein kann, muß sie auch eine eulersche Pseudoprimzahl zur Basis $a\$ sein. Warum? Für eine eulersche Pseudoprimzahl zur Basis $a\$ gilt $a^{\frac {n-1}{2}}\equiv 1\mod n$ oder es gilt $a^{\frac {n-1}{2}}\equiv n-1\mod n$ .

$a^{\frac {n-1}{2}}$ läßt sich auch als $a^{d\cdot 2^{s-1}}$ schreiben. Wenn nun für $n\$ zur Basis $a\$ nun $a^{d}\equiv 1\mod n$ gilt, gilt auch $(a^{d})^{2^{s-1}}\equiv 1\mod n$ und damit auch $a^{d\cdot 2^{s-1}}\equiv 1\mod n$ .

Pseudoprimzahlen

Carmichael-Zahlen

Die Carmichael-Zahl ist eine besondere Form der fermatschen Pseudoprimzahl. In ihren Eigenschaften kommt sie der Primzahl am Nächsten. Sowohl für die Primzahl, als auch für die Carmichael-Zahl gilt der kleine Fermatsche Satz: Für jede ganze Zahl $a\$ gilt $n|a^{n}-a\$ . Erst wenn man diesen Satz modifiziert, ergibt sich ein Unterschied zwischen Primzahl und Carmichael-Zahl.

Für eine Carmichael-Zahl gelten folgende Eigenschaften:

Eine Carmichael-Zahl ist quadratfrei.
Eine Carmichael-Zahl besteht aus mindestens drei Primfaktoren.
Für jeden Primfaktor $p_{i}\$ einer Carmichael-Zahl $c=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$ gilt $p_{i}-1\$ teilt $c-1\$ .
Für alle Basen $a\$ , die zu der Carmichael-Zahl $c\$ teilerfremd sind, gilt $a^{c-1}\equiv 1\mod c$ .

Quadratfreiheit

Warum muß eine Carmichael-Zahl quadratfrei sein? Angenommen es gibt eine Carmichael-Zahl, die nicht quadratfrei ist. Sie hat der Einfachhalber die Form $c=p_{1}^{n}\cdot p_{2}$ mit $n\geq 2$ . Ausserdem sind $p_{1}\$ und $p_{2}\$ Primzahlen. Es gilt also $p_{1}\$ teilt $c\$ . Mit der Kenntnis der Faktorisierung von $c\$ kann man die Carmichael-Funktion $\lambda (c)$ berechnen:

\lambda (c)=\lambda (p_{1}^{n}\cdot p_{2})=\operatorname {kgV} \{\lambda (p_{1}^{n}),\lambda (p_{2})\}=\operatorname {kgV} \{(p_{1}-1)(p_{1}^{n-1}),p_{2}-1\}

Da $c-1\$ durch $\lambda (c)\$ teilbar ist, ist $c-1\$ auch durch $(p_{1}-1)(p_{1}^{n-1})\$ teilbar, und damit gilt dadurch auch daß $c-1\$ durch $p_{1}\$ teilbar ist. Und das führt zu einem Widerspruch.

Es gilt nämlich $p_{1}\$ teilt $c\$ und $p_{1}\$ teilt $c-1\$ . Der Widerspruch liegt darin, das $c\$ und $c-1\$ zueinander teilerfremd sind, also keine gemeinsamen Teiler besitzen. Also ist es nicht möglich, das eine Carmichael-Zahl nicht quadratfrei ist.

mindestens drei Primfaktoren

Jede Carmichael-Zahl besitzt mindestens 3 voneinander verschiedene Primfaktoren.

Beweis: Durch Widerspruch.

Sei $n\$ eine Carmichael-Zahl. Angenommen, $n=p\cdot q$ , wobei $p\$ und $q\$ Primfaktoren seien. Zunächst muss wegen der oben gezeigten Quadratfreiheit gelten, dass $p\neq q$ . Wir können also annehmen, dass $p<q\$ (man kann die Schlüsse analog mit $p>q\$ ziehen). Nun gilt wegen Eigenschaft (3) $q-1|n-1\$ also $q-1|p\cdot q-1$ .

Damit ist ${\frac {p\cdot q-1}{q-1}}=p+{\frac {p-1}{q-1}}\in \mathbb {Z}$ . Das bedeutet aber, $(q-1)|(p-1)\$ im Widerspruch zu $p<q\$ . Also war die Annahme falsch. Carmichael-Zahlen mit 1 Primfaktor kann es nach Definition nicht geben (denn sie sind gerade Pseudo-Primzahlen und selbst keine Primzahlen), und dass es Carmichael-Zahlen mit 3 Primfaktoren gibt, zeigt bereits die allererste: $561=17\cdot 11\cdot 3$ . Zusammen genommen ist also gezeigt worden, eine Carmichael-Zahl besitzt mindestens 3 Primfaktoren.

p_i-1 teilt c-1 für c = p₁·p₂· ... · p_n

Für jeden Primteiler $p_{i}\$ einer Carmichael-Zahl $c\$ gilt, das $p_{i}-1\$ die Zahl $c-1\$ teilt.

Beispiel

1105\

ist das Produkt von

5\

,

13\

und

17\

. Da

1105\

eine Carmichael-Zahl ist, gilt nach dem Korselt-Kriterium:

$4\$ teilt $1104\$	$\Rightarrow {\frac {1104}{4}}=276$
$12\$ teilt $1104\$	$\Rightarrow {\frac {1104}{12}}=92$
und
$16\$ teilt $1104\$	$\Rightarrow {\frac {1104}{16}}=69$

a^c-1 ≡ 1 mod c für alle zu c teilfremden a

Unter den fermatschen Pseudoprimzahlen ist sie die Königin, denn für sie gilt, zu jeder Basis natürlichen Basis $a\geq 2$ zu der die Carmichael-Zahl $c\$ teilerfremd ist, gilt $a^{c-1}\equiv 1\mod c$

Beispiel

Die Zahl

561=3\cdot 11\cdot 17

ist eine Carmichael-Zahl.

Die Zahlen

43\

,

49\

und

65\

sind teilerfremd zur

561\

, also gelten:

43^{560}\equiv 1\mod 561

49^{560}\equiv 1\mod 561

65^{560}\equiv 1\mod 561

Die Zahlen

51\

,

55\

und

57\

sind nicht teilerfremd zur

561\

, also gelten:

51^{560}\not \equiv 1\mod 561

55^{560}\not \equiv 1\mod 561

57^{560}\not \equiv 1\mod 561

Carmichael-Zahlen generieren

Es gibt zwei Wege, an Carmichael-Zahlen zu kommen. Der eine ist, sich zufällig natürliche Zahlen zu erzeugen, um dann auf $a^{c-1}\equiv 1\mod c$ und $\operatorname {ggT} (a,c)=1$ für alle $2\leq a\leq c-2$ zu testen. Der Erfolg, auf diese Weise Carmichael-Zahlen zu finden ist sehr gering. Will man allerdings Carmichael-Zahlen zu vermeiden, so ist dieser Weg vorzuziehen. Der andere Weg ist, konsequent das Produkt aus mindestens drei, zueinander teilerfremden Primzahlen zu bilden, um die so erzeugten Zahlen auf das Korelt-Kriterium zu prüfen.

Nicht jedes quadratfreie Produkt aus Primzahlen kann eine Carmichael-Zahl sein. Ansonsten gäbe es jede Menge Carmichael-Zahlen. Aber kann man bestimmte Primzahlkombinationen schon vorher ausschliessen? Man kann! Es gilt nämlich, das zwei natürliche Zahlen $n\$ und $n-1\$ zueeinander Teilerfremd sind. Das bedeutet, das $n\$ und $n-1\$ keine gemeinsamen Teiler besitzen.

Es ist also wichtig, das bei der generierten Zahl $n=p_{1}\cdot p_{2}\cdot p_{3}\cdot ...p_{n}$ alle $p_{i}\$ zu allen $p_{i}-1\$ teilerfremd sind. Das ist nicht selbstverständlich, wie das folgende Beispiel zeigt:

5\cdot 11\cdot 23\cdot 47=59455

(5-1)\cdot (11-1)\cdot (23-1)\cdot (47-1)=40480

Wichtig an dem Beispiel ist, das (11-1) durch 5 teilbar ist, (23-1) durch 11 und (47-1) durch 23. Ein solches Produkt kann nie eine Carmichael-Zahl sein.

Wenn also die Primzahl $p_{i}\$ Teil einer Carmichael-Zahl sein soll, so sind alle Primzahlen der Form $m\cdot p_{i}+1$ als Teil der Carmichael-Zahl ausgeschlossen.

3	7	13	19	31	37	43	61	67	73	79	...
5	11	31	41	61	71	101	...
7	29	43	71	...

Carmichael-Zahlen nach Chernick

Wenn man sich auf eine spezielle Form der Carmichael-Zahlen beschränken will, dann gibt es noch die Carmichael-Zahlen nach Chernick. Diese haben die allgemeine Form:

M_{k}(m)=(6m+1)(12m+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}m+1)

wobei eine Einschränkung für Carmichael-Zahlen nach Chernick $M_{k}(m)\$ für $m\geq 5\$ existiert:

Für

(36*2^{j}m+1)\

gilt, das die Zahl

m\

durch

2^{j}\

teilbar sein muss.

Für $M_{k}(3)\$ lautet die Formel $(6m+1)\cdot (12m+1)\cdot (18m+1)\$ , die äquivalent zu der Formel $p\cdot (2p-1)\cdot (3p-2)\$ für $p>3\$ ist.

Für $M_{k}(4)\$ lautet die Formel $(6m+1)\cdot (12m+1)\cdot (18m+1)\cdot (36m+1)\$ .

Beweis der Äquivalenz

Warum sind die beiden Konstruktionsvorschriften:

Eine Zahl $M_{3}(m)=(6m+1)(12m+1)(18m+1)$ ist dann eine Carmichael-Zahl,
wenn alle 3 Faktoren $(6m+1)$ , $(12m+1)$ und $(18m+1)$ Primzahlen sind.

und

Sei p > 3 eine Primzahl derart, dass auch 2p-1 und 3p-2 Primzahlen sind,
dann ist n = p(2p-1)(3p-2) eine Carmichael-Zahl

zueinander äquivalent? Es wäre doch möglich, das eine Primzahl $p\$ , die nicht der Form $6m+1\$ entspricht, existiert, so daß $2p-1\$ und $3p-2\$ auch Primzahlen sind. Nun, so eine Primzahl existiert nicht.

Es gibt nur zwei Arten von Primzahlen $p\$ mit $p>3\$ , nämlich Primzahlen der Form $6m+1\$ und Primzahlen der Form $6m-1\$ . Wenn man $p\$ durch $6m-1\$ ersetzt, bekommt man statt $2p-1\$ den Ausdruck $2(6m-1)-1\$ . Ausmultipliziert und zusammengefaßt macht das $12m-3\$ . Dieser Ausdruck ist also stets durch drei teilbar. Nur mit einer Primzahl der Form $6m+1\$ kann man mit der Formel $p\cdot (2p-1)\cdot (3p-2)\$ für $p>3\$ eine Carmichael-Zahl bekommen.

absolute eulersche Pseudoprimzahlen

Eine absolute eulersche Pseudoprimzahl ist eine Carmichael-Zahl, die außerdem zu jeder, zu ihr teilerfremden, Basis $a$ euler-pseudoprim ist.

Pseudoprimzahlen

Die Kunst, eine Pseudoprimzahl nach Maß zu konstruieren

Eine Pseudoprimzahl $q\$ , die zu irgendeiner natürlichen Zahl $a\$ pseudoprim, im Sinne des kleinen fermatschen Satz ist, ist recht einfach. Man nehme zwei beliebige, zueinander teilerfremde Primzahlen $p\$ mit $p\geq 3$ , und multipliziere miteinander. Das Produkt wird dann schon zu wenigstens einer natürlichen Zahl $a\$ pseudoprim sein. Aber zu welcher Zahl $a\$ ? Interessant ist es ja, eine Pseudoprimzahl zu erzeugen, die zu einer vorher ausgewählten Zahl $a\$ pseudoprim ist, ohne sie testen zu müssen.

$a\$ und $q\$ müssen zueinander teilerfremd sein

Damit zusammengesetzte Zahl $q\$ zu einer natürlichen Zahl $a\$ pseudoprim sein kann, muß immerhin sichergestellt sein, das $a\$ und $q\$ zueinander teilerfremd sind. Zu jeder solcher Fermatschen Pseudoprimzahlen der Form $q=p_{1}\cdot p_{2}\$ lassen sich zwei Basen $a\$ finden, und zwar durch folgende Vorgehensweise:

Man ermittelt die Vielfachen von

p_{1}\

und

p_{2}\

:

p_{1},\ 2\cdot p_{1},\ 3\cdot p_{1},\ 4\cdot p_{1},\ 5\cdot p_{1},...

und

p_{2},\ 2\cdot p_{2},\ 3\cdot p_{2},\ 4\cdot p_{2},\ 5\cdot p_{2},...

Dann sucht man jeweils ein Vielfaches $m\cdot p_{1}$ und $n\cdot p_{2}$ heraus, für die $|m\cdot p_{1}-n\cdot p_{2}|=2$ gilt. Die zwischen $m\cdot p_{1}$ und $n\cdot p_{2}$ liegende Zahl ist eine Basis, zu der die Zahl $q=p_{1}\cdot p_{2}$ pseudoprim ist (im Sinne des kleine fermatschen Satzes), und sie ist teilerfremd zu $p_{1},\ p_{2},\ m$ und $n\$ . Es gibt zu jeder Zahl $q=p_{1}\cdot p_{2}$ genau zwei Basen $a\$ die kleiner als $q\$ sind. Die Summe dieser beiden Basen $a_{1}\$ und $a_{2}\$ ist $q\$ . Alle Basen $a\$ , die größer als $q\$ sind und sich nach dem beschriebenen Algorithmus konstruieren lassen, haben entweder die Form $a=a_{1}+m\cdot q$ oder $a=a_{1}+m\cdot q$ .

Beispiel

$391=17\cdot 23$

Die Vielfachen von $17\$ sind: $17,\ 34,\ 51,\ 68,\ 85,\ 102,\ 119,\ 136,\ 153,\ 170,\ 187,\ 204,\ 221,\ 238,\ 255,\ 272,\ ...$

Die Vielfachen von $23\$ sind: $23,\ 46,\ 69,\ 92,\ 115,\ 138,\ 161,\ 184,\ 207,\ 230,\ 253,\ 276,\ ...$

Von diesen Vielfachen haben $136\$ und $138\$ beziehungsweise $253\$ und $255\$ eine Differenz von $2\$ . Die zwischen $136\$ und $138\$ liegende Zahl $137\$ und die zwischen $253\$ und $255\$ liegende Zahl $254\$ sind Basen zu denen die Zahl $391\$ pseudoprim ist.

Die Summe von $137\$ und $254\$ ist $391\$ .

Pseudoprimzahlen

Über das folgende Verfahren hat der Mathematiker Lehmer gezeigt, das unendlich viele fermatsche Pseudoprimzahlen existieren müssen:

Man nimmt eine natürliche Zahl

k\

, die größer, oder auch gleich Fünf ist. Mit dieser Zahl

k\

bildet man die beiden Zahlen

2^{k}-1\

und

2^{k}+1\

. Von diesen beider Zahlen nimmt man jeweils einen Primfaktor. Also je eine Primzahl

p\

und

q\

, so daß gilt:

p\

teilt

2^{k}-1\

und

q\

teilt

2^{k}+1\

. Das Produkt

p\cdot q

ist dann eine fermatsche Pseudoprimzahl zur Basis

2^{k}\

.

Beispiel

Man nimmt als $k\$ die Zahl 6. $2^{6}-1=63=3^{2}\cdot 7$ und $2^{6}+1=65=5\cdot 13$ . Wenn man sich jetzt als $p\$ 7 wählt und als $q\$ 5, dann bekommt man mit $5\cdot 7$ die fermatsche Pseudoprimzahl 35.

k	2^k-1	2^k+1	Pseudoprimzahlen nach Lehmer
5	31	3*11	93, 341
6	3²*7	5*13	15, 35, 39, 91
7	127	3*43	381, 5461
8	3517	257	771, 1285, 4369
9	7*73	3³*19	21, 133, 219, 1387
10	31131	5²*41	15, 55, 123, 155, 451, 1221
11	23*89	3*683	69, 267, 15709, 60787
12	3²57*13	17*241	51, 85, 119, 221, 723, 1205, 1687, 3133
...	...	...	...

fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

Michele Cipolla hat 1904 ein Verfahren zum Erzeugen beliebiger fermatscher Pseudoprimzahlen zu einer beliebigen, natürlichen Basis $a\geq 2\$ gefunden. Dazu benötigt man eine Primzahl, die $a(a^{2}-1)\$ nicht teilt. Warum, das wird weiter unten erklärt.

Mit der Basis $a\$ und der Primzahl $p\$ werden zwei Zahlen $n_{1}\$ und $n_{2}\$ erzeugt:

n_{1}={\frac {a^{p}-1}{a-1}}\ \ n_{2}={\frac {a^{p}+1}{a+1}}

Das Produkt $n=n_{1}\cdot n_{2}\$ ist eine fermatsche Pseudoprimzahl zur Basis $a\$

Erklärung

Die Bedingung, das $p\$ teilerfremd zu $a(a^{2}-1)\$ sein soll, kann auch so formuliert werden: $p\$ soll eine Primzahl sein, die $(a-1)\cdot a\cdot (a+1)\$ nicht teilt. $(a^{2}-1)\$ ist nichts anderes als die dritte Binomische Formel: $(a^{2}-1)=(a-1)\cdot (a+1)\$ . Damit ist sichergestellt, das $p\$ zu $a\$ , $(a-1)\$ und $(a+1)\$ teilerfremd ist.

${\frac {a^{p}-1}{a-1}}$ und ${\frac {a^{p}+1}{a+1}}$ sind beides geometrische Reihen, nämlich:

{\frac {a^{p}-1}{a-1}}=a^{p-1}+a^{p-2}+...+a^{2}+a+1

und

{\frac {a^{p}+1}{a+1}}=

Aus $n_{1}\equiv 1\mod 2p$ und $n_{2}\equiv 1\mod 2p$

folgt, dass auch

n\equiv 1\mod 2p

ist.

Aus $a^{2p}\equiv 1\mod n$

folgt, dass

a^{n-1}\equiv 1\mod n

ist,

so dass n eine Pseudoprimzahl zur Basis a sein muss. Da es unendlich viele Primzahlen gibt, muss es demnach auch unendlich viele Pseudoprimzahlen zu jeder Basis a geben.

eine Liste fermatscher Pseudoprimzahlen zur Basis a nach Michele Cipolla

a	p	n₁	n₂	n=n₁*n₂	Faktoren
2	5	31	11	341	11*31
2	7	127	43	5461	43*127
3	5	121	61	7381	111161
3	7	1093	547	597871	547*1093
2	11	2047	683	1398101	2389683
7	5	2801	2101	5884901	111912801
2	13	8191	2731	22369621	2731*8191
5	7	19531	13021	254313151	2944919531
13	5	30941	26521	809977861	11241130941
3	11	88573	44287	3922632451	2367661*3851
2	17	131071	43691	5726623061	43691*131071
17	5	88741	78881	6999978821	1171101*88741
2	19	524287	174763	91625968981	174763*524287
3	13	797161	398581	317733228541	398581*797161
11	7	1948717	1623931	3164581946527	43453191623931
2	23	8388608	2796203	23456248059221	471784812796203

Pseudoprimzahlen

Die Zeisel-Zahl ist eine nach dem Mathematiker Helmut Zeisel benannte Zahl, die das Produkt wenigstens dreier Primzahlen ist, die einer bestimmten linearen Rekursion genügen. Eine besondere Bedeutung in der Mathematik spielen sie nicht. Aufgrund gewisser Ähnlichkeiten zu den Carmichael-Zahlen, und der Tatsache, dass alle Zeisel-Zahlen auch fermatsche Pseudoprimzahlen zu irgendeiner Basis $a\$ sind, sind die Zeisel-Zahlen hier aufgeführt.

Definition

p₀ = 1

p_n = a·p_n-1 + b

Dabei muss jedes p_n mit $n\geq 1$ eine Primzahl ergeben, und sowohl a als auch b sind für alle p_n konstant. Die Zeisel-Zahl z ist dann das Produkt $p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$ .

Beispiel an der Zeisel-Zahl 1885

Die a ist in dem Beispiel die Zahl 2 und b die Zahl 3.

p₀ = 1
p₁ = a·p₀ + b = 2·1  + 3 = 5
p₂ = a·p₁ + b = 2·5  + 3 = 13
p₃ = a·p₂ + b = 2·13 + 3 = 29

z = p₁ · p₂ · p₃ = 5 · 13 · 29 = 1885

Zusammenhang zwischen den Zeisel-Zahlen und den Carmichael-Zahlen nach J.Chernick

Die Bildungsregel der Carmichael-Zahlen nach J. Chernick lautet (6n+1)*(12n+1)*(18n+1). Diese Bildungsregel ist identisch mit der Bildungsregel für Zeisel-Zahlen mit einem a=1 und b=6n. Demzufolge sind alle Carmichael-Zahlen nach Chernick, die ein Produkt aus drei Primzahlen bilden, auch Zeisel-Zahlen.

Eine Liste von Zeisel-Zahlen

Die Carmichael-Zahlen sind fett geschrieben.

a	b	z_n
1	2	105	357
4	-1	1419	31143
1	6	1729	71319
2	3	1885	51329
3	2	4505	51753
2	5	5719	71943
10	-7	15387	323223
2	9	24211	113171
6	-1	25085	529173
4	3	27559	731127
13	-10	31929	329367
8	-3	54205	537293
3	8	59081	1141131
2	3	114985	51329*61
25	-22	207177	3531303
5	6	208681	1161311
9	-2	233569	761547
28	-25	287979	3591627
1	36	294409	3773109
6	5	336611	1171431
5	8	353977	1373373
17	-12	448585	5731229

a	b	z_n
34	-31	507579	3712383
15	-8	982513	7971447
9	2	1012121	11101911
23	-18	1073305	5972213
8	5	1242709	13109877
49	-46	1485609	31014903
55	-52	2089257	31136163
12	-1	2263811	111311571
4	27	2953711	31151631
33	-28	3077705	51374493
14	-3	3506371	111512111
2	9	3655861	113171*151
36	-31	3973085	51495333
2	59	4648261	61181421
4	33	5069629	37181757
2	65	6173179	67199463
42	-37	6253085	51737229
11	6	6985249	171932129
8	15	7355239	231991607
2	69	7355671	71211491
10	9	7558219	191991999
4	39	8011459	43211883

a	b	z_n
88	-85	8413179	317915667
6	25	8444431	312111291
47	-42	8712985	51939029
48	-43	9271805	51979413
20	-9	9773731	112114211
57	-52	15411785	523313229
3	68	18175361	71281911
5	42	18578113	472771427
6	35	19827641	412811721
9	20	20771801	292812549
3	8	23691481	1141131*401
68	-63	26000605	527718773
5	48	26758057	533131613
10	21	34179391	313313331
14	9	35347159	233314643
77	-72	37605385	531324029
20	-3	38596273	173376737
2	125	42501439	127379883
15	8	43055057	233535303
83	-78	46999705	533727893
8	35	49982899	433793067
3	98	52691801	1014011301

a	b	z_n
2	135	53399449	137409953
30	-17	54177877	1337311173
3	100	55902529	1034091327
1	210	56052361	211421631
9	34	69207769	434213823
65	-58	71550913	739725747
18	5	72730439	234197547
11	26	76724569	374334789
10	33	92835667	434634663
2	165	96916279	1674991163
6	65	104966471	714913011
1	270	118901521	271541811
8	-1	126893905	537293*2341
4	105	133800661	1095412269
29	-10	161164441	1954115679
1	306	172947529	307613919
3	148	177055201	1516011951
15	22	185245273	375778677
5	98	199708657	1036133163
4	123	212122639	1276312647
1	330	216821881	331661991
16	21	222931549	376139829

Geschichte

Der Name "Zeisel-Zahl" wurde vermutlich von Kevin Brown eingeführt, der Zahlen $k$ suchte, für die der Ausdruck $2^{k-1}+k$ eine Primzahl ergibt. In einem Posting in die Usenet-Newsgroup sci.math vom 24. Februar 1994 lieferte Helmut Zeisel die Zahl 1885 als eine weitere Lösung. Später wurde (durch Kevin Brown?) entdeckt, dass die Primfaktoren von 1885 die oben beschriebenene Eigenschaft haben. Ein Name der Art Brown-Zeisel-Zahlen wäre daher passender.

Verallgemeinerung

Man muß sich, bei der Bildung der Zeisel-Zahl nicht auf $p_{0}=1$ beschränken. Auch davon abweichende Werte sind möglich.

Beispiele

$p_{0}=4,\ a=2,\ b=5$

p₀ = 4
p₁ = a·p₀ + b = 2·4  + 5 = 13
p₂ = a·p₁ + b = 2·13 + 5 = 31
p₃ = a·p₂ + b = 2·31 + 5 = 67

z = p₁ · p₂ · p₃ = 13 · 31 · 67 = 27001

$p_{0}=-1,\ a=8,\ b=27$

p₀ = -1
p₁ = a·p₀ + b = 8·-1   + 27 =   19
p₂ = a·p₁ + b = 8·19   + 27 =  179
p₃ = a·p₂ + b = 28·179 + 27 = 1459

z = p₁ · p₂ · p₃ = 19 · 179 · 1459 = 4962059

Weblinks

_{Quelle: Die Zeisel-Zahlen sind aus dem Artikel Zeisel-Zahl von der deutsprachigen de.wikipedia.org entnommen.}

Pseudoprimzahlen

Carmichael-Zahlen

Ein Programm, das eine Liste von Carmichael-Zahlen ausgibt, ist geradezu trivial. Das dem so ist, verdanken wir dem Kriterium von Korselt. Dieses Theorem besagt, das eine Carmichel-Zahl $c\$ eine quadratfrei, aus mindestens drei Primfaktoren bestehende, natürliche Zahl der Form $c=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}\$ ist, so das für jedes $p_{i}\$ gilt, das $p_{i}-1\$ die Zahl $c-1\$ teilt. Daraus folgt, das man sich um den kleinen fermatschen Satz $a^{n-1}\equiv 1\mod n$ nich im geringsten zu kümmern braucht. Neben Korselts Kriterium gibt es auch noch Formeln zum erzeugen spezieller Carmichael-Zahlen. Auch bei diesen Beispielen braucht man sich um den kleinen fermatschen Satz nicht zu kümmern.

zweiter Ansatz

Das folgende Programm benutzt drei ineinander verschachtelte Schleifen, durch die sichergestellt wird, das drei zueinander teilerfremde Primzahlen ausgewählt werden. Aus diesen drei Primzahlen wird ein Produkt gebildet, das die zu testende Zahl darstellt. An dieser Zahl wird nun Korselts Kriterium getestet, was einfach ist, da dem Programm die zu der zu testenden Zahl zugehörigen Primteiler bekannt sind. Ist Korselt Kriterium erfüllt, dann handelt es sich bei der Zahl um eine Carmichael-Zahl, und die Zahl wird, samt Primzahlfaktoren als Carmichael-Zahl ausgegeben.

Details: Die Variable p.0 einthält die Anzahl der unterschiedlichen Primzahlen. In p.1 bis p.(p.0) sind die einzelnen Primzahlen abgelegt.

p.1  = 3
p.2  = 5
p.3  = 7
p.4  = 11
p.4  = 13
p.5  = 17
p.6  = 19
p.7  = 23
p.8  = 29
p.9  = 31
p.10 = 37
.
.
.
p.549 = 4001
p.550 = 4003
p.551 = 4007
p.552 = 4013
p.553 = 4019
p.554 = 4021
p.555 = 4027
p.556 = 4049
p.557 = 4051
p.558 = 4057
i=558
do a=1 to (i-2)
  do b=a+1 to (i-1)
    do c=b+1 to i
      t = 0
      z=p.a*p.b*p.c
      ax=p.a-1
      bx=p.b-1
      cx=p.c-1
      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)
      if (pz = 0) then t = 1
      if (t = 1) then do
        say z||"="||p.a||"*"||p.b||"*"||p.c
        lineout("rcrmn___.txt",z||" = "||p.a||"*"||p.b||"*"||p.c)
      end
      t=0
    end
  end
end

Das Programm kann man modifizieren, indem man die Anzahl der Prizahlen erhöht. Für Carmichel-Zahlen mit mehr als drei Primfaktoren muß man die Anzahl der Schleifen erhöhen, und die Prüfroutinen erweitern.

Carmichael-Zahlen nach Chernick

Die Carmichel-Zahlen nach Chernick sind nur ein kleiner Ausschnitt aus den Carmichael-Zahlen. Sie lassen sich durch folgende Formel generieren: $M_{3}(n)=(6n+1)\cdot (12n+1)\cdot (18n+1)\$ . Es gibt dabei allerdings zwei Einschränkungen:

keine der drei Terme $(6n+1)\$ , $(12n+1)\$ und $(18n+1)\$ darf eine Quadratzahl ergeben, der ganze Ausdruck $M_{3}(n)=(6n+1)\cdot (12n+1)\cdot (18n+1)\$ muß quadratfrei sein.
Jede der drei Terme $(6n+1)\$ , $(12n+1)\$ und $(18n+1)\$ muß eine Primzahl sein. Halt, hier gibt es eine Ausnahme: Wenn eine einzige der drei Terme eine fermatsche Pseudoprimzahl oder selbst eine Carmichael-Zahl ist, so ist $M_{3}(n)\$ trotzdem eine Carmichael-Zahl.

Alle gültigen $n\$ für eine Carmichael-Zahlen nach Chernick enden mit einer 0, einer 1 einer 5 oder einer 6.

l.1  = 0
l.2  = 1
l.3  = 5
l.4  = 6
do i = 0 to 1000
  do j = 1 to 4
    n=i+l.j
    m=(6*n+1)*(12*n+1)*(18*n+1)
    if((primzahl(6*n+1)=true) && (primzahl(12*n+1)=true) && (primzahl(18*n+1)=true)) then do
      say m||"="||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1)
      lineout("rcrmn___.txt",m||" = "||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1))
    end
  end
end

Das Programm läßt sich entsprechend der Formeln für Carmichael-Zahlen nach Chernick, mit mehr als drei Primzahlfaktoren, nach der entsprechenden Formel erweitern.

absolute Eulersche Pseudoprimzahlen

Das Programm, mit dem oben Carmichael-Zahlen erzeugt werden, kann man mit einer kleinen Modifikation dazu bringen, absolute eulersche Pseudoprimzahlen zu erzeugen:

      zax=(z-1)/2
      pz=(zax // ax) + (zax // bx) + (zax // cx)

statt

      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)

Das hierbei alle absoluten eulerschen Pseudoprimzahlen ausgegeben werden, ist eine andere Frage. Aber die Zahlen, die ausgegeben werden, sind absolute Eulersche Pseudoprimzahlen.

Mod_Up

Da man es bei der Berechnung von fermatschen Pseudoprimzahlen häufig mit großen Potenzen großer Zahlen zu tun bekommt, hat man ein kleines Problem. Zum Beispiel für den Nachweis, das 341 eine fermatsche Pseudoprimzahl zur Basis 2 ist, muß man die Zahl $2^{340}\$ berechnen. Diese Zahl heißt ausgeschrieben:

2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776

Das ist für ein Programm wie MuPad wahrscheinlich kein Problem, für die meisten herkömmlichen Programmiersprachen aber sehr wohl. Durch eine Kombination von Multiplikation und Modulo kann man aber auch wesentlich größere Potenten kleinhalten.

Beispiel: $5^{6}=15625\$ >. Letztendlich interessiert uns ja aber nicht $5^{6}=15625\$ , sondern vielmehr $5^{6}\mod n$ mit sagen wir mal $n=7\$ . Das ist $5^{6}\mod 7=1\$ . Nun läßt sich $5^{6}\mod 7\$ auch so ausdrücken:

(((((((((5*5)\mod 7)*5)\mod 7)*5)\mod 7)*5)\mod 7)*5)\mod 7

Dabei wird der Wert 7 niemals überschritten.

/* REXX-Programm */
say 'Only a Library!'
exit 1
/* */
/* */
m_u: procedure
  arg a,l,m
/* initialisierung */
  as = a
  ai = a
  li = (l-1)
  DO li
    a = a * ai
    a = a // m
  END
return a

Fermatsche Pseudoprimzahlen

Eine Primzahl unterscheidet von fermatschen Primzahlen und Carmichael-Zahlen dadurch, das der kleine fermatsche Satz $a^{n-1}\equiv 1\mod n$ für alle Basen $a\$ mit $2\leq a<n$ gilt. Carmichael-Zahlen unterscheiden sich von normalen Pseudoprimzahlen das der Anteil von Basen $a\$ mit $2\leq a<n$ für die $a^{n-1}\equiv 1\mod n$ gilt, größer gleich 97% beträgt. Der einfachheithaber benutzt man als als Basen $a\$ nur die Primzahlen die kleiner als die zu testende Zahl $n\$ ist. Das Programm testet also zu jeder Primbasis $a\$ ob eine Zahl $n\$ die Bedingung $a^{n-1}\equiv 1\mod n$ erfüllt. Erfüllt sie es, dann wird die Variable tm1 = 1 gesetzt, und gleichzeitig die Zählvariable tm3 um eins erhöht. Erfüllt die Zahl $n\$ die Bedingung nicht, dann wird die Variable tm2 = 2 gesetzt. Nach ablauf der Tests wird die Variable gtm = tm1 + tm2 gesetzt. Aus gtm und dtm läßt sich ablesen, ob es sich bei der Zahl $n\$ um eine Primzahl, eine fermatsche Pseudoprimzahl oder eine Carmichael-Zahl handelt.

gtm	dtm	Art der Zahl
1	-	Primzahl
3	tm3 < dtm	fermatsche Pseudoprimzahl
3	tm3 >= dtm	Carmichael-Zahl

/* Ein Programm, zur Ermittlung von Primzahlen, Pseudoprimzahlen */
/* und Charmichaelzahlen (starke Pseudoprimzahlen) */
/* Ein extrem langsames Programm */

#include <stdio.h>

int primfeld[400000];
int tst[400000];

unsigned long modup(unsigned long x, unsigned long y)
{
  unsigned long mindex, xtemp = 1;
  for(mindex=1;mindex<=(y-1);mindex++)
  {
    xtemp *= x;
    xtemp %=y;
  }
  return(xtemp);
} 

int main()
{
  unsigned long index, index2, anzp=1, m, dtm;
  int tm1, tm2, tm3, gtm;
  FILE *prim;
  FILE *pspr;
  FILE *cnbr;
  prim = fopen("prim.dat","w");
  pspr = fopen("pspr.dat","w");
  cnbr = fopen("cnbr.dat","w");
  primfeld[1] = 2;
  for(index=3;index<=4000000;index++)
  {
    tm1 = 0;
    tm2 = 0;
    tm3 = 0;
    /* faktor$ = "" */
    for(index2=1;index2<=anzp;index2++)
    {
      m = modup(primfeld[index2], index);
      tst[index2] = m;
      if (m == 1)
      {
        tm1 = 1;
        tm3++;
      }
      if ( m != 1) { tm2 = 2; }
    }
    gtm = tm1 + tm2;
    if (gtm == 1)
    {
      anzp++;
      primfeld[anzp] = index;
      fprintf(prim,"%d \n",index);
    }
    if (gtm == 3)
    {
      dtm=anzp/2;
      if (tm3 < dtm)
      {
        fprintf(pspr,"%d: ",index);
        for(index2=1;index2<=anzp;index2++)
        {
          m = modup(primfeld[index2], index);
          if (m == 1)
          {
            fprintf(pspr,"%d, ",primfeld[index2]);
          }
        }
        fprintf(pspr,"\n",0);
      }
      if (tm3 >= dtm)
      {
        fprintf(pspr,"%d: ",index);
        for(index2=1;index2<=anzp;index2++)
        {
          m = modup(primfeld[index2], index);
          if (m != 1)
          {
            fprintf(cnbr,"N%d, ",primfeld[index2]);
          }
        }
        fprintf(cnbr,"\n",0);
      }
    }
  }
  fclose(prim);
  fclose(pspr);
  fclose(cnbr);
  return 0;
}

Nachteil des Programms: Es wird schnell sehr langsam. Ausserdem ist es für einige Pseudoprimzahlen blind. So besitzt die Zahl 39 keine Primzahlen $p\ <39$ zu denen die 39 pseudoprim wäre.

Pseudoprimzahlen

Was unterscheidet aⁿ ≡ a (mod n) von a^n-1 ≡ 1 (mod n)

Für jede Primzahl $p\$ gilt, das für jede natürliche Zahl $a\$ der Ausdruck $a^{p}-a\$ durch $p\$ teilbar ist. Ebenso gilt für jede Carmichael-Zahl $c\$ , das für jede natürliche Zahl $a\$ der Ausdruck $a^{c}-a\$ durch $c\$ teilbar ist.

Ja aber bitte wie unterscheidet man dann eine Primzahl von einer Carmichael-Zahl?

Es gibt natürlich noch andere Wege, um an das Problem zu gehen, aber dafür hilft auch eine Modifikation des kleinen Fermatschen Satzes:

Für jede Primzahl

p\

gilt:

a^{p-1}\equiv 1(\mod p)

für jede natürliche Zahl

a\

, die teilerfremd zu

p\

ist.

Das bedeutet, das der kleine fermatsche Satz für $a=p\$ nicht gilt: $p^{p-1}\not \equiv 1(\mod p)$ . Ähnliches gilt für jede Carmichael-Zahl $c\$ : $c^{c-1}\not \equiv 1(\mod c)$ . Aber es gilt genauso für alle Primteiler $p_{m}\$ der entsprechenden Carmichael-Zahl $c=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$ : $c^{p_{n}-1}\not \equiv 1(\mod c)$ .

2 ≤ a ≤ n-2 statt 2 ≤ a ≤ n-1

Pseudoprimzahlen

Potenzen

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:

2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,...\

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

a,a^{2},a^{3},a^{4},a^{5},a^{6},...\

Ein Feld solcher Zahlen sieht so aus:

	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 $n\$ zu dem man das Ganze Modulo nimmt, und und der die Einheit nach unten begrenzt, und andererseits die Carmichael-Funktion $\lambda (n)$ die der kleinste gemeinsame Faktor darstellt, zu der für jeden, zu $n\$ teilerfremden Wert $a\$ gilt: $a^{\lambda (n)}\equiv 1\mod n$

Muster

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

natürliche Zahlen

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 $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:

	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

...

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion $a^{\lambda (n)}$ 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 $a^{\frac {\lambda (n)}{2}}$ zurückgeliefert werden.

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

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

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

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: $n-1\$ muß durch $\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.

	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

Selbstreferenzierende Spalte

Wie ja schon bekannt ist, gilt für eine Primzahl $p\$ , das für jede zu $p\$ teilerfremde Basis $a\$ $a^{p-1}\equiv 1\mod p$ 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 $p-1\$ aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl $p=13\$ das $(p-1)=12=2\cdot 2\cdot 3$ ist, sich also z.B. in $2\cdot 6$ und $3\cdot 4$ zerlegen läßt. Das bedeutet, wenn sich ein Exponent $n\$ in zwei Faktoren $r\$ uns $s\$ zerlegen läßt, das $(a^{r})^{s}=(a^{s})^{r}=a^{r\cdot s}=a^{n}$ gilt.

Beispiele:

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

	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

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.

Eine Primzahl hat viele Eigenschaften, an denen man sie als Primzahl erkennen kann. Dementsprechend gibt es viele Verfahren, um eine Zahl auf ihre primalität zu prüfen. Ein Teil dieser Verfahren ist 100 prozentig sicher, dafür aber auch unheimlich zeitaufwendig. Für Primzahlen mit hundert und mehr Stellen würde eine Menscheleben nicht ausreichen, wenn man diese Primzahl nach diesen Verfahren auf Primalität Testen würde. Der andere Teil der Verfahren kann relativ schnell ein Ergebnis ausgeben, ob eine Zahl eine Primzahl ist, oder nicht. Dafür sind die Verfahren aber für Pseudoprimzahlen anfällig. Dabei sind sind die Primzahlen aber nicht von gleicher Qualität. Einige Pseudoprimzahlen lassen sich leicht ausschliessen, dafür sind andere Pseudoprimzahlen richtig hartnäckig.

Pseudoprimzahlen $n$ ,

die zu allen Basen $a\$ , zu denen sie eine fermatsche Pseudoprimzahl ist, auch eine eulersche Pseudoprimzahl ist.

die zu allen Basen $a\$ , zu denen sie teilerfremd ist, eine fermatsche Pseudoprimzahl ist (Carmichael-Zahlen).

die zu allen Basen $a\$ , zu denen sie teilerfremd ist, sowohl eine fermatsche Pseudoprimzahl, als auch eulersche Pseudoprimzahl ist (absolute eulersche Pseudoprimzahl).

Ich kenne von einer Pseudoprimzahl nur die Primzahlbasen zu denen die Pseudoprimzahl pseudoprim ist, möchte aber alle Basen bekommen, zu denen die Pseudoprimzahl pseudoprim ist, ohne jede natürliche Zahl $\leq 2$ zu testen.

Beispiel 65:

die Primzahlbasen (a<65) zur Pseudoprimzahl 65 sind 31, 47 und 53.

Demzufolge ist 65 auch zu allen Potenzen dieser Primzahlen pseudoprim:

n	31	mod 65	47	mod 65	53	mod 65
2	961	51	2209	64	2809	14
3	29791	21	103823	18	148877	27
4	923521	1	4789681	1	7890481	1

Damit haben wir als Basen (a<65), zu denen die Pseudoprimzahl 65 pseudoprim ist, die Zahlen 14, 18, 21, 27, 31, 47, 51, 53 und 64. Jetzt fehlen noch die Basen der Form (65 - a):

65 - 53 = 12; 65 - 51 = 14; 65 - 47 = 18; 65 - 31 = 34; 65 - 27 = 38; 65 - 21 = 44; 65 - 18 = 47; 65 - 14 = 51.

Nun haben wir alle Basen a mit a<65, zu denen die 65 Pseudoprim ist: 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53 und 64.

Halt: es fehlen noch 8 und 57.

Pseudoprimzahlen

Offene Fragen bezüglich der Pseudoprimzahlen

1. Existiert eine Pseudoprimzahl, die keine fermatsche Pseudoprimzahl ist?

Diese Frage muß man aufspalten in mehrere Aspekte:

1.1. Existiert eine Pseudoprimzahl, die nicht gleichzeitig eine fermatsche Pseudoprimzahl ist?

Wenn es gültig ist, das

(n+1)^{n-1}\equiv 1\mod n\

für eine zusammengesetzte natürliche Zahl

n\

als kriterium für eine fermatsche Pseudoprimzahl ausreicht, was noch nicht sicher ist, dann ist jede Zahl, die nach irgendeinem Kriterium Pseudoprimzahl ist, auch eine fermatsche Pseudoprimzahl.

1.2.a. Läßt sich jedes beliebige Kriterium aufgrund dessen Pseudoprimzahlen existieren, auf den kleinen fermatschen Satz zurückführen?

1.2.b. Gibt es ein noch stärkeres Kriterium, auf das sich der kleine fermatsche Satz zurückführen läßt und auf das sich noch andere Kriterien zurückführen lassen, die ansonsten aber keine Gemeinsamkeiten mit dem kleinen fermatschen Satz besitzen?

Anhänge
zeitliche Abfolge
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen

Geschichte der Pseudoprimzahl

ca. 500 v. Chr

Chinesische Mathematiker glaubten, für natürliche Zahlen $n\$ , dass wenn $2\cdot (2^{n-1}-1)\$ durch $n\$ teilbar ist, dieses $n\$ eine Primzahl sein muß. Ausmultipliziert erhält man die Formel $2^{n}-2\$

1640

Der französische Amateurmathematiker Pierre de Fermat schreibt Mersenne, das wenn $p\$ eine Primzahl ist, $p\$ die Zahl $2^{p}-2\$ teilt. Fermat schrieb Mersenne auch, das ein Beweis dieses Satzes zu lange wäre, als das er ihm ihn zusenden könnte. Dieser Satz ist als kleiner fermatscher Satz bekannt geworden.

1819

Sarrus findet mit der Zahl $341=11\cdot 31$ ein Beispiel, daß es auch zusammengesetzte Zahlen gibt, die den kleinen fermatschen Satz erfüllen. Diese Zahl wird auch Sarrus-Zahl genannt, und ist die kleinste zusammengesetzte Zahl, die den kleinen fermatschen Satz zur Basis 2 erfüllt.

1899

Der deutsche Mathematiker Alwin Reinhold Korselt stellt das nach ihm benannte korseltsche Kriterium auf:

Es existieren ungerade, quadratfreie natürliche Zahlen $n$ , so dass $a^{n}-a$ für alle natürlichen Zahlen $a$ ein Vielfaches von $n$ ist
Für alle Primteiler $p$ von $n$ gilt, dass $p-1$ die Zahl $n-1$ teilt.

1903

Der Mathematiker Malo, und ein Jahr Später der Mathematiker Cipolla finden jeweils einen Beweis für die Existenz von unendlich vielen Pseudoprimzahlen.

1910

Robert Daniel Carmichael findet, mit 561, als erster eine Zahl, die dem korseltschen Kriterium genügt. Nach ihm werden Zahlen dieser Art Carmichael-Zahlen genannt. 561 ist die kleinste Carmichael-Zahl.

1936

D.H Lehmer findet eine simple Methode, beliebig viele fermatsche Pseudoprimzahlen zu erzeugen:

Man nehme eine natürliche Zahl

k\

mit

k\geq 5

. Daraus ermittele man zwei natürliche Zahlen

p\

und

q\

, wobei

p\

ein Primfaktor von

2^{k}-1\

und

q\

ein Primfaktor von

2^{k}+1\

ist. Das Produkt

p\cdot q

ist eine fermatsche Pseudoprimzahl.

1939

J.Chernik macht die Bemerkung, daß das Produkt $(6n+1)(12n+1)(18n+1)$ eine Carmichael-Zahl ist, wenn alle drei Faktoren Primzahlen sind.

1950

N.G.W.H. Beeger führt den Begriff der Carmichael-Zahl ein. Ein Jahr später findet Beeger einen Beweis für die Existenz von unendlich vielen geraden Pseudoprimzahlen.

1992

Die Mathematiker Alford, Granville und Pomerance finden einen Beweis für die Existenz von unendlich vielen Carmichael-Zahlen.

Pseudoprimzahlen

Anhänge
zeitliche Abfolge
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen

Robert Daniel Carmichael

(* 1. März 1879 in Goodwater, Alabama, USA, † 1967)

Michele Cipolla

(* 28. Oktober 1880 in Palermo, † 7. September 1947 in Palermo)

Leonhard Euler

(* 15. April 1707 in Riehen (Schweiz), † 18. September 1783 in St. Petersburg)

Pierre de Fermat

Pierre de Fermat (* Ende 1607 oder Anfang 1608 in Beaumont-de-Lomagne, † 12. Januar 1665 in Castres) war ein französischer Jurist und Amateurmathematiker. Seine besonderen Leistungen liegen in dem kleinen fermatschen Satz und dem großen fermatschen Satz $a^{n}+b^{n}=c^{n}$ , zu dem Fermat die Behauptung aufgestellt hat, dass es für $n>2$ keine Lösung in ganzen Zahlen gibt. Diese Vermutung wurde erst Ende des 20. Jahrhunderts, also nach mehr als 300 Jahren, bewiesen. Auf Pierre de Fermat geht auch die Vermutung, dass alle Zahlen der Form $F_{n}=2^{2^{n}}+1$ Primzahlen sind. Diese Vermutung wurde 1732 von Leonhard Euler widerlegt. Nach Fermat heißt diese Art von Zahl Fermat-Zahl. Der deutsche Mathematiker Christian Goldbach verwendete die Fermat-Zahlen in seinem Beweis, dass es unendlich viele Primzahlen geben muss.

Alwin Reinhold Korselt

(* 17. März 1864 in Mittelherwigsdorf, † 4. Februar 1947 in Plauen)

Pseudoprimzahlen

Anhänge
zeitliche Abfolge
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen

Pseudoprimzahlen

Anhänge
zeitliche Abfolge
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen

Formelsammlung

Um die Pseudoprimzahlen zu verstehen, muss man ein paar Dinge wissen.

Der kleine Fermatsche Satz

Der kleine fermatsche Satz besagt, das für eine Primzahl $p\$ und jede natürliche Zahl $a\geq 2$ gilt, das $a^{p}-a\$ teilbar durch $p\$ ist. Beispiel anhand der Primzahl 5:

$2^{5}-2=5\cdot 6$
$3^{5}-3=5\cdot 48$
$4^{5}-4=5\cdot 204$

Ableitungen

Statt der Aussage: " $a^{p}-a\$ ist (ohne Rest) durch $p\$ teilbar", kann man auch $a^{p}\equiv a\mod p$ schreiben. Wenn man $a\$ aus $a^{p}-a\$ ausklammert, bekommt man auf einen Ausdruck $a\cdot (a^{p-1}-1)\$ . Da $a\cdot (a^{p-1}-1)\$ durch $p\$ teilbar ist, aber $a\$ nicht zwangsläufig durch $p\$ teilbar ist, muß es der Ausdruck $(a^{p-1}-1)\$ sein, der immer durch $p\$ teilbar ist. Aus der Aussage: " $a^{p-1}-1\$ ist durch $p\$ teilbar", kann man $a^{p-1}\equiv 1\mod p$ ableiten. Für die Aussage: " $a^{p-1}-1\$ ist durch $p\$ teilbar" und die Formel $a^{p-1}\equiv 1\mod p$ gilt allerdings, das die Basis $a\$ teilerfremd zur Primzahl $p\$ ist.

Die Division

Wenn man 23 durch 8 dividiert, bekommt man 2,875 als Ergebnis. Man kann die Division aber auch mit Rest auffassen: 23 dividiert durch 8 ist gleich 2 Rest 7. Dieser Rest wird auch Modulo genannt. Das läßt sich durch die folgende Operation ausdrücken: $23\mod 8=7$ . Wenn zwei Divisionen mit gleichem Divisor den gleichen Modulo zurückliefern, sind sie zuenander kongruent. Zum Beispiel hat 29 dividiert durch 11 den Rest 7 und 73 dividiert durch 11 hat auch den Rest 7. Also sind 29 und 73 in Bezug auf die Division durch 11 kongruent. Mathematisch wird das wie folgt ausgedrückt: $29\equiv 73\mod 11$ . Der Rest (Modulo) einer Division ist immer kongruent zu dem Dividenden. Also ist Beispielsweise $23\equiv 7\mod 8$ , da $23=2\cdot 8+7$ und $7=0\cdot 8+7$ ist.

Der Sonderfall

Bezogen auf die ganzen Zahlen ist $(n-1)\mod n$ immer $(n-1)\$ . Das gleiche trifft auch auf $(bn-1)\$ zu, also alle Vielfachen von $n\$ minus eins. Beispielsweise gilt für die Zahl 7: $27\equiv 20\equiv 13\equiv -1\equiv 6\mod 7$ . In der Tat gilt für jede natürliche Zahl größer gleich drei: $-1\equiv (n-1)\mod n$ . Es ist daher von Vorteil statt $x\equiv (n-1)\mod n$ besser $x\equiv -1\mod n$ zu schreiben.

eulersche φ-Funktion

Die eulersche φ-Funktion $\varphi (n)$ liefert zu jeder natürlichen Zahl $n\$ die Anzahl der zu $n\$ teilerfremden Zahlen zurück. Da die eulersche φ-Funktion $\varphi (n)$ auch ein Vielfaches der Carmichael-Funktion $\lambda (n)\$ ist, gilt $a^{\varphi (n)}\equiv 1\mod n$ für jedes $a\$ teilerfremd zu $n\$ .

Die eulersche φ-Funktion wird wie folgt berechnet:

$\varphi (1)=1$
$\varphi (p^{r})=p^{r-1}\cdot (p-1)\quad {\text{für }}p>2{\text{ prim}},r\geq 1$
$\varphi (p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdot \dots \cdot p_{s}^{r_{s}})=\varphi (p_{1}^{r_{1}})\cdot \varphi (p_{2}^{r_{2}})\cdot \dots \cdot \varphi (p_{s}^{r_{s}})$

Carmichael-Funktion

Die Carmichael-Funktion $\lambda (n)\$ einer natürlichen Zahl $n\$ liefert als Funktionswert die kleinste, natürliche Zahl zurück, so das für jede zu $n\$ teilerfremde Basis $a\$ mit $a>1\$ gilt: $a^{\lambda (n)}\equiv 1\mod n$ .

Die Carmichael-Funktion wird wie folgt berechnet:

$\lambda (1)=1\$
$\lambda (2)=1,\quad \lambda (4)=\lambda (8)=2,\quad \lambda (2^{r})=2^{r-2}{\text{ für }}r\geq 2$
$\lambda (p^{r})=p^{r-1}\cdot (p-1)\quad {\text{für }}p>2{\text{prim}},r\geq 1$
$\lambda (p_{1}^{r_{1}}p_{2}^{r_{2}}\cdot \cdot \cdot p_{s}^{r_{s}})=\operatorname {kgV} \{\lambda (p_{1}^{r_{1}}),\lambda (p_{2}^{r_{2}}),\dots ,\lambda (p_{s}^{r_{s}})\}$

eulerscher Satz

Auf den kleinen fermatschen Satz läßt sich die dritte binomische Formel $a^{2}-b^{2}=(a+b)\cdot (a-b)$ anwenden. $a^{p-1}-1\equiv 0\mod p=(a^{\frac {p-1}{2}}+1)\cdot (a^{\frac {p-1}{2}}-1)\equiv 0\mod p$ . Das bedeutet, das genau eine der beiden Möglichkeiten zutreffen muß, daß also $a^{\frac {p-1}{2}}+1$ durch $p\$ teilbar sein muß, oder $a^{\frac {p-1}{2}}-1$ muß durch $p\$ teilbar sein. Das führt zu dem Satz, der Leonhard Euler zugesprochen wird: Wenn $p\$ eine ungerade Primzahl ist, dann muß entweder $a^{\frac {p-1}{2}}\equiv 1\mod p$ gelten oder es muß $a^{\frac {p-1}{2}}\equiv -1\mod p$ gelten.

Das Korselt-Kriterium

Der deutsche Mathematiker Alwin Reinhold Korselt hat 1899 ein Kriterium für eine bestimmte Art von Pseudoprimzahlen aufgestellt, von denen er aber kein Exemplar mehr finden konnte. Im Jahr 1910 kam ihm der Mathematiker Robert Daniel Carmichael, mit dem Finden der kleinsten Zahl, auf die das Korselt-Kriterium zutrifft, zuvor.

Es existieren ungerade, quadratfreie natürliche Zahlen $n$ , so dass $a^{n}-a$ für alle natürlichen Zahlen $a$ ein Vielfaches von $n$ ist
Für alle Primteiler $p$ von $n$ gilt, dass $p-1$ die Zahl $n-1$ teilt.

Eine Pseudoprimzahl, die diese Bedingungen erfüllt, muß also quadratfrei sein, was bedeutet das für diese Pseudoprimzahl der Form $q=p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdot \dots \cdot p_{n}^{r_{n}}$ kein $r_{i}\$ größer als eins sein darf. Ausserdem muß gelten, das bei $q=p_{1}\cdot p_{2}\cdot \dots \cdot p_{n}$ für jedes $p_{i}\$ folgendes gültig ist: $p_{i}-1\$ teilt $q-1\$

Die allgemeinen Lucas-Folgen

Die beiden allgemeinen Lucas-Folgen $U(P,Q)\$ und $V(P,Q)\$ , deren jeweilige einzelne Glieder $U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}$ bzw. $V_{n}(P,Q)=a^{n}+b^{n}\$ sind, lassen sich über die Quadratische Gleichung $x^{2}-Px+Q=0\$ ableiten, deren beide Lösungen $a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}$ und $b={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}$ sind.

Zwischen den Allgemeinen Lucas-Folgen und den Primzahlen gibt es einen Zusammenhang: Wenn die natürliche Zahl $n\$ eine Primzahl ist, dann gilt $n\$ teilt $V_{n}(P,Q)-P\$ für alle Folgen deren $P>0\$ und $Q=\pm 1$

Daraus folgt, daß wenn $n\$ eine zusammengesetze Zahl ist, und trotzdem $n\$ teilt $V_{n}(P,Q)-P\$ gilt, $n\$ eine Pseudoprimzahl zu $V_{n}(P,Q)\$ ist.

Pseudoprimzahlen

Anhänge
zeitliche Abfolge
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen

Irrtümer zu Pseudoprimzahlen

Wer sich mit Pseudoprimzahlen beschäftigt, wird früher oder später in die eine oder andere Falle laufen. Stärker als bei den Primzahlen scheint man immer wieder auf Muster zu stoßen, die sich aber bei genauerer Prüfung sich in Luft auflösen. Um solche Irrtümer geht es hier.

Zu jeder fermatschen Pseudoprimzahl q existiert mindestens eine Primzahl p mit p kleiner als q, so daß q pseudoprim zu p ist

Die Zahl 39 ist ein Beispiel dafür, das dem nicht so ist. Denn die einzigen Zahlen kleiner 39, zu denen die 39 pseudoprim ist, sind die 14 und die 25. Die erste Primzahl zu der 39 pseudoprim ist, ist die 53.

Pseudoprimzahlen

Glossar

B

Beweis

N

natürliche Zahl

P

Primzahl

Eine Primzahl ist eine natürliche Zahl größer Eins, die nur durch Eins und sich selber teilbar ist.

Weitergehendes ist unter Primzahlen zu finden.

U

Umkehrschluss

Legende

n,a	-	natürliche Zahlen
p	-	Primzahl
q	-	Pseudoprimzahl
c	-	Carmichael-Zahl
PsP(a)	-	fermatsche Pseudoprimzahl zur Basis a
ePsP(a)	-	eulersche Pseudoprimzahl zur Basis a
sPsP(a)	-	starke Pseudoprimzahl zur Basis a

Pseudoprimzahlen

Anhänge
zeitliche Abfolge
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen

Literatur

The New Book of Prime Number Records, Paulo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5
Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7

Internet

Wikipedia:

andere Quellen
- Final Answers Modular Arithmetic
- Zeisel Number from MathWorld
- MathPages - Zeisel Numbers
- The On-Line Encyclopedia of Integer Sequences (OEIS)
- Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Was soll das Buch bezwecken?

Warum dieses Buch?

Für wen ist dieses Buch gedacht?

Ein rechenintensives Thema

Unterscheidung

Was sind Pseudoprimzahlen

Der umgekehrte Weg

Die fermatsche Pseudoprimzahl im allgemeinen

Ein paar Daten zu den fermatschen Pseudoprimzahlen

Die fermatsche Pseudoprimzahl

Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

Die fermatsche Pseudoprimzahl

Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

Eulersche Pseudoprimzahl

Ableitung der eulerschen Pseudoprimzahl aus der fermatschen Pseudoprimzahl

die starke Pseudoprimzahl

Zerlegung

781 zur Basis 5

1541 zur Basis 5

25 zur Basis 7

305 zur Basis 11

starke Pseudoprimzahl und eulersche Pseudoprimzahl

Carmichael-Zahlen

Quadratfreiheit

mindestens drei Primfaktoren

pi -1 teilt c-1 für c = p1 ·p2 · ... · pn

ac-1 ≡ 1 mod c für alle zu c teilfremden a

Carmichael-Zahlen generieren

Carmichael-Zahlen nach Chernick

Beweis der Äquivalenz

absolute eulersche Pseudoprimzahlen

Die Kunst, eine Pseudoprimzahl nach Maß zu konstruieren

a {\displaystyle a\ } und q {\displaystyle q\ } müssen zueinander teilerfremd sein

Beispiel

Beispiel

fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

Erklärung

eine Liste fermatscher Pseudoprimzahlen zur Basis a nach Michele Cipolla

Definition

Beispiel an der Zeisel-Zahl 1885

Zusammenhang zwischen den Zeisel-Zahlen und den Carmichael-Zahlen nach J.Chernick

Eine Liste von Zeisel-Zahlen

Geschichte

Verallgemeinerung

Beispiele

Weblinks

Carmichael-Zahlen

zweiter Ansatz

Carmichael-Zahlen nach Chernick

absolute Eulersche Pseudoprimzahlen

Mod_Up

Fermatsche Pseudoprimzahlen

Was unterscheidet an ≡ a (mod n) von an-1 ≡ 1 (mod n)

2 ≤ a ≤ n-2 statt 2 ≤ a ≤ n-1

Potenzen

Muster

natürliche Zahlen

Primzahlen

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

Abgrenzung der Primzahlen von anderen natürlichen Zahlen

Carmichael-Zahlen

Pseudoprimzahlen

Selbstreferenzierende Spalte

pure eulersche Pseudoprimzahl

ca. 500 v. Chr

1640

1819

1899

1903

1910

1936

1939

1950

1992

Robert Daniel Carmichael

Michele Cipolla

Leonhard Euler

Pierre de Fermat

Alwin Reinhold Korselt

Der kleine Fermatsche Satz

p_i-1 teilt c-1 für c = p₁·p₂· ... · p_n

a^c-1 ≡ 1 mod c für alle zu c teilfremden a

$a\$ und $q\$ müssen zueinander teilerfremd sein

Was unterscheidet aⁿ ≡ a (mod n) von a^n-1 ≡ 1 (mod n)