Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Carmichael-Zahl aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Carmichael-Zahl

Eine Carmichael-Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, ist eine spezielle eulersche_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.
1994 bewiesen Pomerance, Alford und Granville die Existenz unendlich vieler Carmichael-Zahlen. Alford, W. R.; Granville, A.; and Pomerance, C.: "There are Infinitely Many Carmichael Numbers." Ann. Math. 139 (1994), 703-722

Einleitung

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.

Definition einer Carmichael-Zahl

Vorbemerkung zur Kongruenz und zum Modulo

:$a\; \backslash equiv\; b\; \backslash mod\; c$ wird ?$a$ ist kongruent zu $b$ modulo $c$? gesprochen, und ist genau dann der Fall, wenn $a\; -\; b$ ein ganzzahliges Vielfaches von $c$ ist.

Definition

Eine zusammengesetzte natürliche Zahl $q$ heißt Carmichael-Zahl, falls für alle zu $q$ teilerfremden Zahlen $a$ gilt:
:$a^\{q-1\}\; \backslash equiv\; 1\backslash quad(\{\backslash rm\; mod\backslash \; \}\; q)$

Beispiel

561 = 3*11*17 ist die kleinste Carmichael-Zahl.
Für alle Basen $a$, die keinen Primfaktor mit 561 gemeinsam haben, gilt:
:$a^\{560\}\; \backslash equiv\; 1\backslash quad\; (\{\backslash rm\; mod\backslash \; \}\; 561)$


561 ist durch 3, 11, 17, 33, 51 und 187 teilbar. Für diese Teiler gilt $a^\{q-1\}\; \backslash equiv\; 1\backslash quad\; (\{\backslash rm\; mod\backslash \; \}\; q)$ nicht!
:$3^\{560\}\; \backslash equiv\; 375\; \backslash quad\; (\{\backslash rm\; mod\backslash \; \}\; 561)$
:$11^\{560\}\; \backslash equiv\; 154\; \backslash quad\; (\{\backslash rm\; mod\backslash \; \}\; 561)$
:$17^\{560\}\; \backslash equiv\; 34\; \backslash quad\; (\{\backslash rm\; mod\backslash \; \}\; 561)$
: u. s. w.

Das Theorem von Alwin Korselt

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 Zahl $c-1$ teilen.

Folgerung

Aus der Tatsache, dass $p\_i-1|c-1$ kann man für alle $a\backslash$ folgern, dass $a^c\; \backslash equiv\; a\; \backslash ,\backslash pmod\; c$

Beweis

oBdA: $p\_1\; \backslash dots\; p\_i\; |\; a$

:$a^\{c\}\; \backslash equiv\; 0\; \backslash equiv\; a\; \backslash ,\backslash pmod\{p\_1\}$
:$\backslash vdots$
:$a^\{c\}\; \backslash equiv\; 0\; \backslash equiv\; a\; \backslash ,\backslash pmod\{p\_i\}$
:$a^c\; \backslash equiv\; a^\{c-1\}\backslash cdot\; a\; \backslash equiv\; a^\{(p\_\{i+1\}-1)\; \backslash cdot\; b\_\{i+1\}\}\; \backslash cdot\; a\; \backslash equiv\; a\; \backslash ,\backslash pmod\{p\_\{i+1\}\}$
:$\backslash vdots$
:$a^c\; \backslash equiv\; a^\{c-1\}\backslash cdot\; a\; \backslash equiv\; a^\{(p\_\{n\}-1)\; \backslash cdot\; b\_\{n\}\}\; \backslash cdot\; a\; \backslash equiv\; a\; \backslash ,\backslash pmod\{p\_\{n\}\}$

Nach dem Produkt der Primzahlen 7, 13, 31 und 61. Es gilt:
:$172081\; -\; 1\; =\; (7\; -\; 1)\; *\; 28680$
:$172081\; -\; 1\; =\; (13\; -\; 1)\; *\; 14340$
:$172081\; -\; 1\; =\; (31\; -\; 1)\; *\; 5736$
:$172081\; -\; 1\; =\; (61\; -\; 1)\; *\; 2868$

Verschärfung

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

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\backslash in\; P$ gilt:
:$p-1$ teilt $\backslash frac\{n\}\{p\}-1$

Beispiel

Für die Carmichael-Zahl 172081 = 7 * 13 * 31 * 61 gilt:
:$\backslash frac\{172081\}\{7\}\; -\; 1\; =\; 24583\; -\; 1\; =\; (7\; -\; 1)\; *\; 4097$


:$\backslash frac\{172081\}\{13\}\; -\; 1\; =\; 13237\; -\; 1\; =\; (13\; -\; 1)\; *\; 1103$


:$\backslash frac\{172081\}\{31\}\; -\; 1\; =\; 5551\; -\; 1\; =\; (31\; -\; 1)\; *\; 185$


:$\backslash frac\{172081\}\{61\}\; -\; 1\; =\; 2821\; -\; 1\; =\; (61\; -\; 1)\; *\; 47$

Robert Daniel Carmichael

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.

Carmichael-Zahlen allgemein

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 1994 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

Carmichael-Zahlen nach J. Chernick (Carmichael-Zahl-Generator)

J. Chernick fand 1939 ein relativ einfaches System um Carmichael-Zahlen zu konstruieren:Äquivalent dazu ist der Satz:

Unter anderem haben folgende Carmichael-Zahlen diese Struktur:

p (2p-1) (3p-2)
M₃(m) (6m + 1) (12m + 1) (18m + 1) m
---------------------------------------------------------------
Tabelle_mathematischer_Symbole

Weblinks

*
• Final Answers Modular Arithmetic
• Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim

       VIDEO-NEWS UND ANGEBOTE