Pseudoprimzahlen: Formelsammlung

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


Anhänge
zeitliche Abfolge
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen


Formelsammlung

Um die Pseudoprimzahlen zu verstehen, muss man ein paar Dinge wissen.

Der kleine Fermatsche Satz[Bearbeiten]

Der kleine fermatsche Satz besagt, das für eine Primzahl und jede natürliche Zahl gilt, das teilbar durch ist. Beispiel anhand der Primzahl 5:

Ableitungen[Bearbeiten]

Statt der Aussage: " ist (ohne Rest) durch teilbar", kann man auch schreiben. Wenn man aus ausklammert, bekommt man auf einen Ausdruck . Da durch teilbar ist, aber nicht zwangsläufig durch teilbar ist, muß es der Ausdruck sein, der immer durch teilbar ist. Aus der Aussage: " ist durch teilbar", kann man ableiten. Für die Aussage: " ist durch teilbar" und die Formel gilt allerdings, das die Basis teilerfremd zur Primzahl ist.

Die Division[Bearbeiten]

Wenn man 23 durch 8 dividiert, bekommt man 2,875 als Ergebnis. Man kann die Division aber auch mit Rest auffassen: 23 dividiert durch 8 ist gleich 2 Rest 7. Dieser Rest wird auch Modulo genannt. Das läßt sich durch die folgende Operation ausdrücken:. Wenn zwei Divisionen mit gleichem Divisor den gleichen Modulo zurückliefern, sind sie zuenander kongruent. Zum Beispiel hat 29 dividiert durch 11 den Rest 7 und 73 dividiert durch 11 hat auch den Rest 7. Also sind 29 und 73 in Bezug auf die Division durch 11 kongruent. Mathematisch wird das wie folgt ausgedrückt: . Der Rest (Modulo) einer Division ist immer kongruent zu dem Dividenden. Also ist Beispielsweise , da und ist.

Der Sonderfall[Bearbeiten]

Bezogen auf die ganzen Zahlen ist immer . Das gleiche trifft auch auf zu, also alle Vielfachen von minus eins. Beispielsweise gilt für die Zahl 7: . In der Tat gilt für jede natürliche Zahl größer gleich drei:. Es ist daher von Vorteil statt besser zu schreiben.

eulersche φ-Funktion[Bearbeiten]

Die eulersche φ-Funktion liefert zu jeder natürlichen Zahl die Anzahl der zu teilerfremden Zahlen zurück. Da die eulersche φ-Funktion auch ein Vielfaches der Carmichael-Funktion ist, gilt für jedes teilerfremd zu .

Die eulersche φ-Funktion wird wie folgt berechnet:

Carmichael-Funktion[Bearbeiten]

Die Carmichael-Funktion einer natürlichen Zahl liefert als Funktionswert die kleinste, natürliche Zahl zurück, so das für jede zu teilerfremde Basis mit gilt: .

Die Carmichael-Funktion wird wie folgt berechnet:

eulerscher Satz[Bearbeiten]

Auf den kleinen fermatschen Satz läßt sich die dritte binomische Formel anwenden. . Das bedeutet, das genau eine der beiden Möglichkeiten zutreffen muß, daß also durch teilbar sein muß, oder muß durch teilbar sein. Das führt zu dem Satz, der Leonhard Euler zugesprochen wird: Wenn eine ungerade Primzahl ist, dann muß entweder gelten oder es muß gelten.

Das Korselt-Kriterium[Bearbeiten]

Der deutsche Mathematiker Alwin Reinhold Korselt hat 1899 ein Kriterium für eine bestimmte Art von Pseudoprimzahlen aufgestellt, von denen er aber kein Exemplar mehr finden konnte. Im Jahr 1910 kam ihm der Mathematiker Robert Daniel Carmichael, mit dem Finden der kleinsten Zahl, auf die das Korselt-Kriterium zutrifft, zuvor.

  1. Es existieren ungerade, quadratfreie natürliche Zahlen , so dass für alle natürlichen Zahlen ein Vielfaches von ist
  2. Für alle Primteiler von gilt, dass die Zahl teilt.

Eine Pseudoprimzahl, die diese Bedingungen erfüllt, muß also quadratfrei sein, was bedeutet das für diese Pseudoprimzahl der Form kein größer als eins sein darf. Ausserdem muß gelten, das bei für jedes folgendes gültig ist: teilt

Die allgemeinen Lucas-Folgen[Bearbeiten]

Die beiden allgemeinen Lucas-Folgen und , deren jeweilige einzelne Glieder bzw. sind, lassen sich über die Quadratische Gleichung ableiten, deren beide Lösungen und sind.

Zwischen den Allgemeinen Lucas-Folgen und den Primzahlen gibt es einen Zusammenhang: Wenn die natürliche Zahl eine Primzahl ist, dann gilt teilt für alle Folgen deren und

Daraus folgt, daß wenn eine zusammengesetze Zahl ist, und trotzdem teilt gilt, eine Pseudoprimzahl zu ist.