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.
Beispiel: die Carmichael-Zahl 172081 ist ein Produkt aus den Primzahlen 7, 13, 31 und 61:
Definition einer Carmichael-Zahl
Vorbemerkung zur Kongruenz und zum Modulo
Definition:
Für alle Carmichael-Zahlen q gilt, dass alle Basen a mit , die nicht Teiler von q sind:
Als Beispiel dafür sei die 561 (sie ist die kleinste Carmichael-Zahl) angeführt:
Eigenschaft der Teilbarkeit:
Für eine Carmichael-Zahl gilt, dass alle die die Zahl teilen.
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 |
1899 stellte A.Korselt ein Theorem auf:
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, 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.
J. Chernick fand 1939 ein relativ einfaches System um Carmichael-Zahlen zu konstruieren:
rote Zahlen sind Pseudoprimzahlen
grüne Zahlen sind Carmichael-Zahlen
Die kleinste Carmichaelzahl mit mehr als 3 Primfaktoren, die sich mit dem oben beschriebenen Bildungsgesetz bilden lässt, ist die .
Gérard P. Michon fand einen gänzlich anderen Weg, um Carmichael-Zahlen zu konstruieren:
Das Theorem von A.Korselt
Korselt selbst hat so eine Zahl nie gefunden.Robert Daniel Carmichael
Carmichael-Zahlen allgemein
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)
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)
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. 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)
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)
Literatur
- The New Book of Prime Number Records, Paolo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5
Links
- Final Answers Modular Arithmetic
- Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim