Pseudoprimzahlen: Makropseudoprimzahlen

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Pseudoprimzahlen

Carmichael-Zahlen[Bearbeiten]

Die Carmichael-Zahl ist eine besondere Form der fermatschen Pseudoprimzahl. In ihren Eigenschaften kommt sie der Primzahl am Nächsten. Sowohl für die Primzahl, als auch für die Carmichael-Zahl gilt der kleine Fermatsche Satz: Für jede ganze Zahl gilt . Erst wenn man diesen Satz modifiziert, ergibt sich ein Unterschied zwischen Primzahl und Carmichael-Zahl.

Für eine Carmichael-Zahl gelten folgende Eigenschaften:

  1. Eine Carmichael-Zahl ist quadratfrei.
  2. Eine Carmichael-Zahl besteht aus mindestens drei Primfaktoren.
  3. Für jeden Primfaktor einer Carmichael-Zahl gilt teilt .
  4. Für alle Basen , die zu der Carmichael-Zahl teilerfremd sind, gilt .

Quadratfreiheit[Bearbeiten]

Warum muß eine Carmichael-Zahl quadratfrei sein? Angenommen es gibt eine Carmichael-Zahl, die nicht quadratfrei ist. Sie hat der Einfachhalber die Form mit . Ausserdem sind und Primzahlen. Es gilt also teilt . Mit der Kenntnis der Faktorisierung von kann man die Carmichael-Funktion berechnen:

Da durch teilbar ist, ist auch durch teilbar, und damit gilt dadurch auch daß durch teilbar ist. Und das führt zu einem Widerspruch.

Es gilt nämlich teilt und teilt . Der Widerspruch liegt darin, das und zueinander teilerfremd sind, also keine gemeinsamen Teiler besitzen. Also ist es nicht möglich, das eine Carmichael-Zahl nicht quadratfrei ist.

mindestens drei Primfaktoren[Bearbeiten]

Jede Carmichael-Zahl besitzt mindestens 3 voneinander verschiedene Primfaktoren.

Beweis: Durch Widerspruch.

Sei eine Carmichael-Zahl. Angenommen, , wobei und Primfaktoren seien. Zunächst muss wegen der oben gezeigten Quadratfreiheit gelten, dass . Wir können also annehmen, dass (man kann die Schlüsse analog mit ziehen). Nun gilt wegen Eigenschaft (3) also .

Damit ist . Das bedeutet aber, im Widerspruch zu . Also war die Annahme falsch. Carmichael-Zahlen mit 1 Primfaktor kann es nach Definition nicht geben (denn sie sind gerade Pseudo-Primzahlen und selbst keine Primzahlen), und dass es Carmichael-Zahlen mit 3 Primfaktoren gibt, zeigt bereits die allererste: . Zusammen genommen ist also gezeigt worden, eine Carmichael-Zahl besitzt mindestens 3 Primfaktoren.

pi -1 teilt c-1 für c = p1 ·p2 · ... · pn [Bearbeiten]

Für jeden Primteiler einer Carmichael-Zahl gilt, das die Zahl teilt.

  • Beispiel
ist das Produkt von , und . Da eine Carmichael-Zahl ist, gilt nach dem Korselt-Kriterium:
teilt
teilt
und
teilt


ac-1 ≡ 1 mod c für alle zu c teilfremden a[Bearbeiten]

Unter den fermatschen Pseudoprimzahlen ist sie die Königin, denn für sie gilt, zu jeder Basis natürlichen Basis zu der die Carmichael-Zahl teilerfremd ist, gilt

  • Beispiel
Die Zahl ist eine Carmichael-Zahl.
Die Zahlen , und sind teilerfremd zur , also gelten:
Die Zahlen , und sind nicht teilerfremd zur , also gelten:


Carmichael-Zahlen generieren[Bearbeiten]

Es gibt zwei Wege, an Carmichael-Zahlen zu kommen. Der eine ist, sich zufällig natürliche Zahlen zu erzeugen, um dann auf und für alle zu testen. Der Erfolg, auf diese Weise Carmichael-Zahlen zu finden ist sehr gering. Will man allerdings Carmichael-Zahlen zu vermeiden, so ist dieser Weg vorzuziehen. Der andere Weg ist, konsequent das Produkt aus mindestens drei, zueinander teilerfremden Primzahlen zu bilden, um die so erzeugten Zahlen auf das Korelt-Kriterium zu prüfen.

Nicht jedes quadratfreie Produkt aus Primzahlen kann eine Carmichael-Zahl sein. Ansonsten gäbe es jede Menge Carmichael-Zahlen. Aber kann man bestimmte Primzahlkombinationen schon vorher ausschliessen? Man kann! Es gilt nämlich, das zwei natürliche Zahlen und zueeinander Teilerfremd sind. Das bedeutet, das und keine gemeinsamen Teiler besitzen.

Es ist also wichtig, das bei der generierten Zahl alle zu allen teilerfremd sind. Das ist nicht selbstverständlich, wie das folgende Beispiel zeigt:

Wichtig an dem Beispiel ist, das (11-1) durch 5 teilbar ist, (23-1) durch 11 und (47-1) durch 23. Ein solches Produkt kann nie eine Carmichael-Zahl sein.

Wenn also die Primzahl Teil einer Carmichael-Zahl sein soll, so sind alle Primzahlen der Form als Teil der Carmichael-Zahl ausgeschlossen.

3 7 13 19 31 37 43 61 67 73 79 ...
5 11 31 41 61 71 101 ...
7 29 43 71 ...

Carmichael-Zahlen nach Chernick[Bearbeiten]

Wenn man sich auf eine spezielle Form der Carmichael-Zahlen beschränken will, dann gibt es noch die Carmichael-Zahlen nach Chernick. Diese haben die allgemeine Form:

wobei eine Einschränkung für Carmichael-Zahlen nach Chernick für existiert:

Für gilt, das die Zahl durch teilbar sein muss.

Für lautet die Formel , die äquivalent zu der Formel für ist.

Für lautet die Formel .

Beweis der Äquivalenz[Bearbeiten]

Warum sind die beiden Konstruktionsvorschriften:

Eine Zahl ist dann eine Carmichael-Zahl,
wenn alle 3 Faktoren , und Primzahlen sind.

und

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

zueinander äquivalent? Es wäre doch möglich, das eine Primzahl , die nicht der Form entspricht, existiert, so daß und auch Primzahlen sind. Nun, so eine Primzahl existiert nicht.

Es gibt nur zwei Arten von Primzahlen mit , nämlich Primzahlen der Form und Primzahlen der Form . Wenn man durch ersetzt, bekommt man statt den Ausdruck . Ausmultipliziert und zusammengefaßt macht das . Dieser Ausdruck ist also stets durch drei teilbar. Nur mit einer Primzahl der Form kann man mit der Formel für eine Carmichael-Zahl bekommen.

absolute eulersche Pseudoprimzahlen[Bearbeiten]

Eine absolute eulersche Pseudoprimzahl ist eine Carmichael-Zahl, die außerdem zu jeder, zu ihr teilerfremden, Basis euler-pseudoprim ist.