Infos Home | Impressum | Original Artikel & Autoren Liste

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.

Inhalt
1 Definition einer Carmichael-Zahl
2 Warum die Carmichael-Zahlen keine perfekten Pseudoprimzahlen sind
3 Das Theorem von A.Korselt
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
9

Definition einer Carmichael-Zahl

Vorbemerkung zur Kongruenz und zum Modulo

wird "a ist kongruent zu b in Bezug auf modulo von c" gesprochen.

Definition:

Für alle Carmichael-Zahlen q gilt, dass alle Basen a mit , die nicht Teiler von q sind:
gilt.

Als Beispiel dafür sei die 561 (sie ist die kleinste Carmichael-Zahl) angeführt:
Die 3, 11, 17, 33, 51 und 187 sind Teiler von 561. Für sie gilt nicht:
Basis 3:
Basis 11:
Basis 17:

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

Eigenschaft der Teilbarkeit:

Für eine Carmichael-Zahl gilt, dass alle die die Zahl teilen.

Beispiel: die Carmichael-Zahl 172081 ist ein Produkt aus den Primzahlen 7, 13, 31 und 61:
geteilt durch ist gleich 28680
geteilt durch ist gleich 14340
geteilt durch ist gleich 5736
geteilt durch ist gleich 2868
geteilt durch ist gleich 1912

Das Theorem von A.Korselt

1899 stellte A.Korselt ein Theorem auf:
Es existieren ungerade, natürliche Zahlen n für die gilt, dass sie alle an-a (für alle natürlichen a) ohne Rest dividieren, wenn n quadratfrei ist.
und
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.

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

rote Zahlen sind Pseudoprimzahlen
grüne Zahlen sind Carmichael-Zahlen
Das Bildungsgesetz
lässt sich verallgemeinern:
.
Dieses Bildungsgesetz hat allerdings noch eine kleine Einschränkung: Abgesehen davon, dass alle Faktoren Primzahlen sein müssen, gilt zusätzlich, dass für die Zahl m durch 2j teilbar sein muss.

Die kleinste Carmichaelzahl mit mehr als 3 Primfaktoren, die sich mit dem oben beschriebenen Bildungsgesetz bilden lässt, ist die .

 M4(m) (6m + 1) (12m + 1) (18m + 1) (36m + 1) m
----------------------------------------------------------------------------
 63973 = 7 * 13 * 19 * 37 1 M4(1)
 192739365541 = 271 * 541 * 811 * 1621 45 M4(45)
 461574735553 = 337 * 673 * 1009 * 2017 56 M4(56)
 10028704049893 = 727 * 1453 * 2179 * 4357 121 M4(121)
 84154807001953 = 1237 * 2473 * 3709 * 7417 206 M4(206)
197531244744661 = 1531 * 3061 * 4591 * 9181 255 M4(255) 
973694665856161 = 2281 * 4561 * 6841 * 13681 380 M4(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 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=10329-4624879 die eine 1000 stellige Carmichael-Zahl erzeugt, ergeben sich die drei folgenden Faktoren:

(12936*10329-59827428149)(14784*10329-68374203599)(20328*10329-94014529949)


Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.