Pseudoprimzahlen: Absolute Fermatsche 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 Primzahlen als auch für Carmichael-Zahlen 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.

Carmichael-Zahlen haben folgende Eigenschaften:

1. Eine Carmichael-Zahl ist quadratfrei.
2. Eine Carmichael-Zahl hat mindestens drei Primfaktoren.
3. Für jeden Primfaktor $p_i$ einer Carmichael-Zahl $c=p_1\cdot p_2\cdot \mathrm{...}\cdot p_n$ gilt $p_i-1$ teilt $c-1$.
4. Für alle Basen $a$, die zu einer Carmichael-Zahl $c$ teilerfremd sind, ist $a^{c-1}\equiv 1(\mathrm{mod}c)$.

Quadratfreiheit

Warum muss eine Carmichael-Zahl quadratfrei sein? Angenommen es gibt eine Carmichael-Zahl, die nicht quadratfrei ist. Sie hat der Einfachheit halber die Form $c=p_1^n\cdot p_2$ mit $n\ge 2$. Außerdem 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)=\mathrm{kgV}\{\lambda (p_1^n),\lambda (p_2)\}=\mathrm{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 dass $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, dass $c$ und $c-1$ zueinander teilerfremd sind, also keinen gemeinsamen Teiler besitzen. Also ist es nicht möglich, dass 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\ne 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 nur einem Primfaktor kann es nach Definition nicht geben (denn sie sind 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, dass eine Carmichael-Zahl mindestens 3 Primfaktoren hat.

Satz von Korselt

Der deutsche Mathematiker Alwin Reinhold Korselt hat 1899 ein Theorem über eine bestimmte Art von Pseudoprimzahlen, die später Carmichael-Zahlen genannt wurden, aufgestellt:

1. Es existieren ungerade, quadratfreie natürliche Zahlen $c$, so dass $a^c-a$ für alle natürlichen Zahlen $a$ ein Vielfaches von $c$ ist
2. Für alle Primteiler $p$ von $c$ gilt, dass $p-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 Satz von Korselt:

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

Pseudoprim zu allen zu c teilfremden Basen a

Unter den fermatschen Pseudoprimzahlen ist sie die Königin, denn für sie gilt, mit jeder natürlichen Zahl $a\ge 2$, zu der die Carmichael-Zahl $c$ teilerfremd ist,

$a^{c-1}\equiv 1(\mathrm{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 1mod561$

$49^{560}\equiv 1mod561$

$65^{560}\equiv 1mod561$

Die Zahlen $51$, $55$ und $57$ sind nicht teilerfremd zur $561$, also gelten:

$51^{560}\equiv ̸1mod561$

$55^{560}\equiv ̸1mod561$

$57^{560}\equiv ̸1mod561$

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(\mathrm{mod}c)$ und $\mathrm{ggT}(a,c)=1$ für alle $2\le a\le c-2$ zu testen. Die Wahrscheinlichkeit, auf diese Weise Carmichael-Zahlen zu finden ist sehr gering. Will man allerdings Carmichael-Zahlen 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 Korselt-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 ausschließen? Man kann! Es gilt nämlich, dass zwei natürliche Zahlen $n$ und $n-1$ zueinander teilerfremd sind. Das bedeutet, dass $n$ und $n-1$ keine gemeinsamen Teiler besitzen.

Es ist also wichtig, dass bei der generierten Zahl $n=p_1\cdot p_2\cdot p_3\cdot \mathrm{...}{p}_n$ alle $p_i$ zu allen $p_j-1$ teilerfremd sind. Das ist nicht selbstverständlich, wie das folgende Beispiel zeigt:

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

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

Wenn also die Primzahl $p_i$ Teiler einer Carmichael-Zahl sein soll, so sind alle Primzahlen der Form $m\cdot p_i+1$ als Teiler der Carmichael-Zahl ausgeschlossen.

$p_i$	$m\cdot p_i+1$
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 alle Faktoren Primzahlen sind, und für k > 4 die Zahl $m$ durch $2^{k-4}$ 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 zu jeder, zu ihr teilerfremden, Basis $a$ euler-pseudoprim ist.

Für jeden Primteiler $p_i$ einer absoluten Eulerschen Pseudoprimzahl $n$ gilt:

$p_i-1$ teilt $\frac{n-1}{2}$.

Die ersten absoluten Eulerschen Pseudoprimzahlen sind 1729, 2465, 15841, 41041, 46657, 75361.

Es gibt keine absoluten Euler-Jacobi-Pseudoprimzahlen.

Häufigkeit und Überschneidung mit Lucas-Pseudoprimzahlen

Anzahl der Carmichael-Zahlen und Überschneidung
mit starken und Lucas-Pseudoprimzahlen

				gleichzeitig Carmichael- &
Obergrenze x	Carmichael	f(x)(I)	abs epsp	sPsp(2)	lpsp	Lucas-Psp 2. Art(7,*)
10 3	1	0.014	0	0	0	0
10 4	7	0.072	2	0	0	0
10 5	16	0.054	6	3	0	0
10 6	43	0.047	16	5	0	0
10 7	105	0.050	45	11	0	0
10 8	255	0.042	124	19	0	0
10 9	646	0.036	306	43	0	0
1010	1547	0.031	740	87	0	0
1011	3605	0.024	1736	171	0	0
1012	8241	0.019	4011	316	0	0
1013	19279	0.015	9362	621	0	0
1014	44706	0.012	21974	1153	0	0
1015	105212	0.009	52221	2234	0	0
1016	246683	0.007	122608	4185	0	0

^(I) Vorlage:AnkerMittlerer Anteil falscher Zeugen beim Miller-Rabin-Test.