Mathe Genie Lexikon Carmichael-Zahl Erklärung Bedeutung und Formel

Carmichael-Zahl

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

Inhaltsverzeichnis

1 Einleitung

2 Definition einer Carmichael-Zahl

2.1 Vorbemerkung zur Kongruenz und zum Modulo
2.2 Definition:
2.3 Beispiel

3 Das Theorem von A.Korselt

3.1 Beispiel:

4 Robert Daniel Carmichael

5 Carmichael-Zahlen allgemein

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

7 Carmichael-Zahlen nach Gerard P. Michon (Carmichael-Zahl Generator)

8 Literatur

9 Links

Einleitung

Es ist einfach, eine Carmichael-Zahl als solche zu erkennen, wenn man ihre sämtlichen Teiler kennt. Dies ist dem Theorem von A. 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 muß.

Definition einer Carmichael-Zahl

Vorbemerkung zur Kongruenz und zum Modulo

$a \equiv b \mod c$ wird "a ist kongruent zu b in Bezug auf modulo von c" gesprochen.

Definition:

Für alle Carmichael-Zahlen q gilt:

Alle Basen a mit $2 \le a < q$ , die nicht Teiler von q sind, liefern $a^{q-1} \mod q = 1$ .

Beispiel

561 (sie ist die kleinste Carmichael-Zahl) = 3*11*17. Daraus ergibt sich, das 561 durch 3, 11, 17, 33, 51 und 187 telibar ist. Für diese Teiler gilt $a^{q-1} \mod q = 1$ nicht:

Basis 3: $3^{560} \mod 561 = ((3^{280} \mod 561)^2) \mod 561 = 375$

Basis 11: $11^{560} \mod 561 = ((11^{280} \mod 561)^2) \mod 561 = 154$

Basis 17: $11^{560} \mod 561 = ((17^{280} \mod 561)^2) \mod 561 = 460$

Für alle anderen Basen a, die keine Teiler von 561 sind, gilt:

$a^{560} \mod 561 = ((a^{280} \mod 561)^2) \mod 561 = 1$

Das Theorem von A.Korselt

1899 hat A.Korselt folgendes Theorem aufgestellt:

1.Es existieren ungerade, natürliche Zahlen n für die gilt, dass sie alle aⁿ-a (für alle natürlichen a)
ohne Rest dividieren, wenn n quadratfrei ist.

2.Für alle Primteiler p von n gilt, dass die Zahl (p-1) die Zahl (n-1) teilt.

Korselt selbst hat so eine Zahl 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 n - 1$ die die Zahl $c - 1$ teilen.

Beispiel:

die Carmichael-Zahl 172081 ist ein Produkt aus den Primzahlen 7, 13, 31 und 61:

$(172081 - 1)$ geteilt durch	$(7 - 1)$	ist gleich	28680
$(172081 - 1)$ geteilt durch	$(13 - 1)$	ist gleich	14340
$(172081 - 1)$ geteilt durch	$(31 - 1)$	ist gleich	5736
$(172081 - 1)$ geteilt durch	$(61 - 1)$	ist gleich	2868

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 mindesten drei Primfaktoren zusammengesetzt sein müssen.

Die kleinste Carmichael-Zahl ist die 561. Für die 561 gilt also: 561 ist nicht pseudoprim zu 3, 11, 17, 33, 51 und 187, welches alle Teiler von 561 sind.

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

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

J. Chernick fand 1939 ein relativ einfaches System um Carmichael-Zahlen zu konstruieren:

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

Äquivalent dazu ist der Satz:

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

Die folgenden Carmichael-Zahlen haben diese Struktur:

                     p       (2p-1)      (3p-2)
       M₃(m)   (6m + 1)   (12m + 1)   (18m + 1)    m
--------------------------------------------------------------
       1729 =        7 *        13 *        19     1   M₃(1)
     172081 =       31 *        61 *        91     5   M₃(5)
     294409 =       37 *        73 *       109     6   M₃(6)
    4463641 =       91 *       181 *       271    15   M₃(15)
   56052361 =      211 *       421 *       631    35   M₃(35)
  118901521 =      271 *       541 *       811    45   M₃(45)
  172947529 =      307 *       613 *       919    51   M₃(51)
  216821881 =      331 *       661 *       991    55   M₃(55)
  228842209 =      337 *       673 *      1009    56   M₃(56)
 1110400109 =      557 *      1153 *      1729    96   M₃(96)
 1299963601 =      601 *      1201 *      1801   100   M₃(100)
 2301745249 =      727 *      1453 *      2179   121   M₃(121)
 9624742921 =     1171 *      2341 *      3511   195   M₃(195)
11346205609 =     1237 *      2473 *      3709   206   M₃(206)
13079177569 =     1297 *      2593 *      3889   216   M₃(216)
21515221081 =     1531 *      3061 *      4591   255   M₃(255)
27278026129 =     1657 *      3313 *      4969   276   M₃(276)
65700513721 =     2221 *      4441 *      6661   370   M₃(370)
71171308081 =     2281 *      4561 *      6841   380   M₃(380)

rote Zahlen sind Pseudoprimzahlen
grüne Zahlen sind Carmichael-Zahlen

Alle diese Carmichael-Zahlen (mit Ausnahme derer, die Pseudoprimzahlen oder Carmichaelzahlen als Faktoren besitzen) sind auch Zeisel-Zahlen mit einem a=1 und b=6n.

Das Bildungsgesetz:

M 3 (m) = (6 m + 1)(12 m + 1)(18 m + 1)

lässt sich verallgemeinern:

$M_k(m) = (6m + 1)(12m + 1)\prod_{i=1}^{k-2}(9 \cdot 2^im+1)$ .

Dieses Bildungsgesetz hat allerdings noch eine kleine Einschränkung: Abgesehen davon, dass alle Faktoren Primzahlen sein müssen, gilt zusätzlich, dass für $(36 * 2 j m + 1)$ die Zahl m durch 2^j teilbar sein muss.

Die kleinste Carmichaelzahl mit mehr als 3 Primfaktoren, die sich mit dem oben beschriebenen Bildungsgesetz bilden lässt, ist die $M 4 (1)63973 = 7 * 13 * 19 * 37$ .

           M₄(m)   (6m + 1)   (12m + 1)   (18m + 1)   (36m + 1)     m
----------------------------------------------------------------------------
          63973 =        7 *        13 *        19 *        37     1   M₄(1)
   192739365541 =      271 *       541 *       811 *      1621    45   M₄(45)
   461574735553 =      337 *       673 *      1009 *      2017    56   M₄(56)
 10028704049893 =      727 *      1453 *      2179 *      4357   121   M₄(121)
 84154807001953 =     1237 *      2473 *      3709 *      7417   206   M₄(206)
197531244744661 =     1531 *      3061 *      4591 *      9181   255   M₄(255) 
973694665856161 =     2281 *      4561 *      6841 *     13681   380   M₄(380)

Carmichael-Zahlen nach Gerard P. Michon (Carmichael-Zahl Generator)

Gérard P. Michon fand einen gänzlich anderen Weg, um Carmichael-Zahlen zu konstruieren:

Ein Produkt dreier Primzahlen der Form (7m+1)*(8m+1)*(11m+1) ist dann eine Carmichael-Zahl, wenn für m gilt:

$m \equiv 326 \mod 616$
m muss durch 3 teilbar sein (ansonsten ist wenigstens einer der drei Faktoren durch 3 teilbar)
zu einem gültigen m muss ein natürliches k existieren, so das m=(1848k+942)

Das gilt für (12936k+1)*(14784k+7537)*(20328k+10363) mit folgendem k

	m	(7m+1)	(8m+1)	(11m+1)
k	(1848k+942)	(12936k+6595)	(14784k+7537)	(20328k+10363)
13	24966	174763	199729	274627
123	228246	1597723	1825969	2510707
218	403806	2826643	3230449	4441867
223	413046	2891323	3304369	4543507
278	514686	3602803	4117489	5661547
411	760470	5323291	6083761	8365171
513	948966	6642763	7591729	10438627
551	1019190	7134331	8153521	11211091
588	1087566	7612963	8700529	11963227

Weitere k sind: 733, 743, 796, 856, 928, 1168, 1226, 1263, 1401, 1533, 1976, 1981, 2013, 2096, 2138, 2241, 2376, 2556, 2676, 2703, 3626, 3703, 3718, 3971, 4008, 4121, 4138, 4163, 4188, 4211, 4313, 4423, 4653, 4656, 4901, 5018, 5278, 5411, 5423, 5538, 5776, 5863, 5908, 6186, 6283, 6623, 6753, 6933, 7501, 7688, 7986, 8181, 8398, 8476, 8651, 8651, 8816, 8916, 8923, ...

Für k=10³²⁹-4624879 die eine 1000 stellige Carmichael-Zahl erzeugt, ergeben sich die drei folgenden Faktoren:

(12936*10³²⁹-59827428149)(14784*10³²⁹-68374203599)(20328*10³²⁹-94014529949)

Literatur

The New Book of Prime Number Records, Paolo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5