Carmichael-Zahl
aus Wikipedia, der freien Enzyklopädie
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. [1]
[Bearbeiten] 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.
[Bearbeiten] Definition einer Carmichael-Zahl
[Bearbeiten] Vorbemerkung zur Kongruenz und zum Modulo
- wird „a ist kongruent zu b modulo c“ gesprochen, und ist genau dann der Fall, wenn a − b ein ganzzahliges Vielfaches von c ist.
[Bearbeiten] Definition
Eine zusammengesetzte natürliche Zahl q heißt Carmichael-Zahl, falls für alle zu q teilerfremden Zahlen a gilt:
[Bearbeiten] Beispiel
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 nicht!
- usw.
[Bearbeiten] 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 = p1 * p2 * p3 * ... * pn gilt, dass alle pi − 1 die Zahl c − 1 teilen.
[Bearbeiten] Folgerung
Aus der Tatsache, dass pi − 1 | c − 1 kann man für alle folgern, dass
Beweis
oBdA:
Nach dem chinesischem Restsatz folgt nun
[Bearbeiten] Beispiel
Die Carmichael-Zahl 172081 ist das 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
[Bearbeiten] Verschärfung
Aufgrund der Identität 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 gilt:
- p − 1 teilt
[Bearbeiten] Beispiel
Für die Carmichael-Zahl 172081 = 7 * 13 * 31 * 61 gilt:
[Bearbeiten] 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.
[Bearbeiten] 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
[Bearbeiten] Carmichael-Zahlen nach J. Chernick (Carmichael-Zahl-Generator)
J. Chernick fand 1939 ein relativ einfaches System um Carmichael-Zahlen zu konstruieren:
Eine Zahl M3(m) = (6m + 1)(12m + 1)(18m + 1) ist dann eine Carmichael-Zahl, |
Äquivalent dazu ist der Satz:
Sei p > 3 eine Primzahl derart, dass auch 2p-1 und 3p-2 Primzahlen sind, |
Unter anderem haben folgende Carmichael-Zahlen 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) 1773289 = 67 * 133 * 199 11 M3(11) 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) 100264053529 = 2557 * 5113 * 7669 426 M3(426) 134642101321 = 2821 * 5641 * 8461 470 M3(470) 168003672409 = 3037 * 6073 * 9109 506 M3(506) 172018713961 = 3061 * 6121 * 9181 510 M3(510) 173032371289 = 3067 * 6133 * 9199 511 M3(511)
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 (36 * 2jm + 1) die Zahl m durch 2j teilbar sein muss.
Die kleinste Carmichael-Zahl mit mehr als 3 Primfaktoren, die sich mit dem oben beschriebenen Bildungsgesetz bilden lässt, ist M4(1) = 63973 = 7 * 13 * 19 * 37.
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)
[Bearbeiten] 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 eine Carmichael-Zahl, wenn gilt:
- drei teilt m (andernfalls ist mindestens einer der drei Faktoren durch 3 teilbar)
- Es existiert k mit 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)
[Bearbeiten] Quellen
- ↑ Alford, W. R.; Granville, A.; and Pomerance, C.: "There are Infinitely Many Carmichael Numbers." Ann. Math. 139 (1994), 703-722
[Bearbeiten] Literatur
- Paolo Ribenboim: The New Book of Prime Number Records. Springer Verlag, 1996, ISBN 0-387-94457-5
[Bearbeiten] Siehe auch
[Bearbeiten] Weblinks
-
Wikibooks: Tabelle von Carmichael-Zahlen – Lern- und Lehrmaterialien
- Final Answers Modular Arithmetic
- Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim