Carmichael-Zahlen

Die Carmichael-Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, ist eine spezielle Form der eulerschen Pseudoprimzahl, für die gilt: Eine Carmichael-Zahl $n$ ist pseudoprim zu allen Basen, die keine gemeinsamen Primfaktoren mit $n$ haben. Jede Carmichael-Zahl ist das Produkt aus mindestens 3 Primzahlen.

Es ist einfach, eine Carmichael-Zahl als solche zu erkennen, wenn man ihre sämtlichen Teiler kennt. Dies ist dem Theorem von Alwin Korselt zu verdanken. So ist es auch einfach, eine Carmichael-Zahl zu erzeugen, zumal Algorithmen wie der nach J. Chernick existieren. Problematisch ist es aber, gerade bei großen Zahlen, zu erkennen, ob es sich bei einer Zahl um eine Carmichael-Zahl handelt. Diese Schwierigkeit haben die Carmichael-Zahlen mit den Primzahlen gemeinsam, denn entweder man führt eine Faktorisierung durch, oder man wendet den kleinen fermatschen Satz auf die Zahl an, wobei man für die Basen, die nicht auf eine Primalität weisen und die bei Primzahlen nicht vorkommen, auf Teilbarkeit testen muss.

Eine zusammengesetzte natürliche Zahl $q$ heißt Carmichael-Zahl, falls für alle zu $q$ teilerfremden Zahlen $a$ gilt:

561 = 3*11*17 ist die kleinste Carmichael-Zahl.

Für alle Basen $a$, die keinen Primfaktor mit 561 gemeinsam haben, gilt:

561 ist durch 3, 11, 17, 33, 51 und 187 teilbar. Für diese Teiler gilt $a^{q-1} \equiv 1\quad ({\rm mod\ } q)$ nicht!

Bereits 1899 hat Alwin Korselt folgendes Theorem aufgestellt:

Korselt selbst hat solche Zahlen jedoch nie gefunden.

Speziell der zweite Teil des Theorems liefert eine Eigenschaft auf die Teilbarkeit der Carmichael-Zahlen:

Für eine Carmichael-Zahl $c = p_1 * p_2 * p_3 * \, \, \, * p_n$ gilt, dass alle $p_i-1$ die die Zahl $c-1$ teilen.

Aus der Tatsache, dass $p_i-1|c-1$ kann man für alle $a\$ folgern, dass $a^c \equiv a \, \mathrm{mod}\, c\$

Beweis

oBdA: $p_1 \dots p_i | a$

Nach dem chinesischem Restsatz folgt nun $a^{c} \equiv a \, \mathrm{mod}\, c$

Die Carmichael-Zahl 172081 ist das Produkt der Primzahlen 7, 13, 31 und 61. Es gilt:

Aufgrund der Identität $n-1 = \dfrac{n}{p}-1+(p-1)\dfrac{n}{p}$ gilt für jeden Primteiler $p$ einer natürlichen Zahl $n$:

Somit lässt sich der zweite Teil von Korselts Satz auch formulieren als:

Eine Zahl $n$ mit der Menge der Primteiler $P$ ist genau dann eine Carmichael-Zahl, wenn für jedes $p\in P$ gilt:

Für die Carmichael-Zahl 172081 = 7 * 13 * 31 * 61 gilt:

Robert Daniel Carmichael hat dann 1910 mit 561 die erste Zahl gefunden, die den Eigenschaften des Theorems von Korselt entspricht. Nach Carmichael wurden dann auch später diese Zahlen benannt.

Neben den oben aufgeführten Bedingungen für Carmichael-Zahlen von Korselt gilt für alle Carmichael-Zahlen, dass sie aus mindestens drei teilerfremden, ungeraden Primfaktoren zusammengesetzt sein müssen.

Seit 1992 weiß man, dass unendlich viele Carmichael-Zahlen existieren.

Die ersten 36 Carmichael-Zahlen

561 = 3 * 11 * 17 52633 = 7 * 73 * 103 294409 = 37 * 73 * 109

1105 = 5 * 13 * 17 62745 = 3 * 5 * 47 * 89 314821 = 13 * 61 * 397

1729 = 7 * 13 * 19 63973 = 7 * 13 * 19 * 37 334153 = 19 * 43 * 409

2465 = 5 * 17 * 29 75361 = 11 * 17 * 31 340561 = 13 * 17 * 23 * 67

2821 = 7 * 13 * 31 101101 = 7 * 11 * 13 * 101 399001 = 31 * 61 * 211

6601 = 7 * 23 * 41 115921 = 13 * 37 * 241 410041 = 41 * 73 * 137

8911 = 7 * 19 * 67 126217 = 7 * 13 * 19 * 73 449065 = 5 * 19 * 29 * 163

10585 = 5 * 29 * 73 162401 = 17 * 41 * 233 488881 = 37 * 73 * 181

15841 = 7 * 31 * 73 172081 = 7 * 13 * 31 * 61 512461 = 31 * 61 * 271

29341 = 13 * 37 * 61 188461 = 7 * 13 * 19 * 109 530881 = 13 * 97 * 421

41041 = 7 * 11 * 13 * 41 252601 = 41 * 61 * 101 552721 = 13 * 17 * 41 * 61

46657 = 13 * 37 * 97 278545 = 5 * 17 * 29 * 113 656601 = 3 * 11 * 101 * 197