Lösung - Primzahlen 05
Carmichael-Zahlen, "Kleiner" Fermat
"kleiner" Fermat: Sei p eine Primzahl und a eine beliebige ganze Zahl, dann gilt für alle a
Beispiel:
p = 11, dann gilt
211 mod 11 = 2
311 mod 11 = 3
411 mod 11 = 4
...
1011 mod 11 = 10
26011 mod 11 = (23*11 + 7)11 mod 11 = 7
(es reicht also, alle Basen < p zu testen!)
Hier haben wir ein starkes Kriterium für Primzahlen - wenn für irgendein ganzes a diese Beziehung nicht erfüllt ist, dann ist p keine Primzahl. Leider gilt die Umkehrung des Fermatschen Satzes nicht - man hätte sonst hier ein einfaches Kriterium für Primzahleigenschaft gefunden.
Pseudoprimzahlen
Zahlen, die die Eigenschaft 2n mod n = 2 erfüllen, aber nicht prim sind, nennt man Pseudoprimzahlen. Die erste Pseudoprimzahl ist 341 = 11 * 31. Sie sind relativ selten.
Carmichaelzahlen
Es gibt Zahlen, die den Fermat-Test mit allen Basen erfüllen und trotzdem nicht prim sind. Diese Zahlen heißen Carmichaelzahlen. Die erste Carmichaelzahl ist 561 = 3 * 11 * 17. Wie man aber sofort ahnen kann, sind Carmichaelzahlen sehr selten.
Hinweis: Wenn eine Zahl den Fermatschen Test besteht, ist es zwar nicht sicher, aber doch sehr wahrscheinlich, dass es sich um eine Primzahl handelt.