Buchgenerator (deaktivieren)

Pseudoprimzahlen: Formelsammlung

Aus Wikibooks

Wechseln zu: Navigation, Suche
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 muß man ein paar Dinge wissen.

Inhaltsverzeichnis

[Bearbeiten] Der kleine Fermatsche Satz

Der kleine fermatsche Satz besagt, das für eine Primzahl p\ und jede natürliche Zahl a \ge 2 gilt, das a^p - a\ teilbar durch p\ ist. Beispiel anhand der Primzahl 5:

  • 2^5-2 = 5 \cdot 6
  • 3^5-3 = 5 \cdot 48
  • 4^5-4 = 5 \cdot 204

[Bearbeiten] Ableitungen

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

[Bearbeiten] Die Division

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:23 \mod 8 = 7. 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: 29 \equiv 73 \mod 11. Der Rest (Modulo) einer Division ist immer kongruent zu dem Dividenden. Also ist Beispielsweise 23 \equiv 7 \mod 8, da 23 = 2\cdot 8 + 7 und 7 = 0\cdot 8 + 7 ist.

[Bearbeiten] Der Sonderfall

Bezogen auf die ganzen Zahlen ist (n-1) \mod n immer (n-1)\ . Das gleiche trifft auch auf (bn-1)\ zu, also alle Vielfachen von n\ minus eins. Beispielsweise gilt für die Zahl 7: 25 \equiv 19 \equiv 13 \equiv -1 \equiv 6 \mod 7. In der Tat gilt für jede natürliche Zahl größer gleich drei: -1 \equiv (n-1) \mod n. Es ist daher von Vorteil statt x \equiv (n-1) \mod n besser x \equiv -1 \mod n zu schreiben.

[Bearbeiten] eulersche φ-Funktion

Die eulersche φ-Funktion \varphi(n) liefert zu jeder natürlichen Zahl n\ die Anzahl der zu n\ teilerfremden Zahlen zurück. Da die eulersche φ-Funktion \varphi(n) auch ein Vielfaches der Carmichael-Funktion \lambda(n)\ ist, gilt a^{\varphi(n)} \equiv 1 \mod n für jedes a\ teilerfremd zu n\ .

Die eulersche φ-Funktion wird wie folgt berechnet:

  • \varphi(1) = 1
  • \varphi(p^r) = p^{r-1}\cdot(p-1)\quad\mathrm{f\ddot ur}\ p>2\ \mathrm{prim},r\geq1
  • \varphi(p_1^{r_1}\cdot p_2^{r_2}\cdot ...\cdot p_s^{r_s}) = \varphi(p_1^{r_1})\cdot \varphi(p_2^{r_2})\cdot ...\cdot \varphi(p_s^{r_s})

[Bearbeiten] Carmichael-Funktion

Die Carmichael-Funktion \lambda(n)\ einer natürlichen Zahl n\ liefert als Funktionswert die kleinste, natürliche Zahl zurück, so das für jede zu n\ teilerfremde Basis a\ mit a > 1\ gilt: a^{\lambda(n)} \equiv 1 \mod n.

Die Carmichael-Funktion wird wie folgt berechnet:

  • \lambda(1) = 1\
  • \lambda(2) = 1,\quad\lambda(4)=\lambda(8)=2,\quad\lambda(2^r) = 2^{r-2}\ \mathrm{f\ddot ur}\ r\geq2
  • \lambda(p^r) = p^{r-1}\cdot(p-1)\quad\mathrm{f\ddot ur}\ p>2\ \mathrm{prim},r\geq1
  • \lambda(p_1^{r_1}p_2^{r_2}\cdot\cdot\cdot p_s^{r_s}) = \operatorname{kgV}\{\lambda(p_1^{r_1}),\lambda(p_2^{r_2}),...,\lambda(p_s^{r_s})\}

[Bearbeiten] eulerscher Satz

Auf den kleinen fermatschen Satz läßt sich die dritte binomische Formel a^2 - b^2 = (a+b)\cdot (a-b) anwenden. a^{p-1} - 1 \equiv 0 \mod p = (a^{\frac{p-1}{2}} + 1)\cdot (a^{\frac{p-1}{2}} - 1) \equiv 0 \mod p. Das bedeutet, das genau eine der beiden Möglichkeiten zutreffen muß, daß also a^{\frac{p-1}{2}} + 1 durch p\ teilbar sein muß, oder a^{\frac{p-1}{2}} - 1 muß durch p\ teilbar sein. Das führt zu dem Satz, der Leonhard Euler zugesprochen wird: Wenn p\ eine ungerade Primzahl ist, dann muß entweder a^{\frac{p-1}{2}} \equiv 1 \mod p gelten oder es muß a^{\frac{p-1}{2}} \equiv -1 \mod p gelten.

[Bearbeiten] Das Korselt-Kriterium

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 n, so dass an − a für alle natürlichen Zahlen a ein Vielfaches von n ist
  2. Für alle Primteiler p von n gilt, dass p − 1 die Zahl n − 1 teilt.

Eine Pseudoprimzahl, die diese Bedingungen erfüllt, muß also quadratfrei sein, was bedeutet das für diese Pseudoprimzahl der Form q = p_1^{r_1}\cdot p_2^{r_2}\cdot ... \cdot p_n^{r_n} kein r_i\ größer als eins sein darf. Ausserdem muß gelten, das bei q = p_1\cdot p_2\cdot ... \cdot p_n für jedes p_i\ folgendes gültig ist: p_i - 1\ teilt q - 1\

[Bearbeiten] Die allgemeinen Lucas-Folgen

Die beiden allgemeinen Lucas-Folgen U(P,Q)\ und V(P,Q)\ , deren jeweilige einzelne Glieder U_n(P,Q)=\frac{a^n-b^n}{a-b} bzw. V_n(P,Q)=a^n+b^n\ sind, lassen sich über die Quadratische Gleichung x^2 - Px + Q = 0\ ableiten, deren beide Lösungen a = \frac{P + \sqrt{P^2 - 4Q}}{2} und b = \frac{P - \sqrt{P^2 - 4Q}}{2} sind.

Zwischen den Allgemeinen Lucas-Folgen und den Primzahlen gibt es einen Zusammenhang: Wenn die natürliche Zahl n\ eine Primzahl ist, dann gilt n\ teilt V_n(P,Q) - P\ für alle Folgen deren P > 0\ und Q = \pm 1

Daraus folgt, daß wenn n\ eine zusammengesetze Zahl ist, und trotzdem n\ teilt V_n(P,Q) - P\ gilt, n\ eine Pseudoprimzahl zu V_n(P,Q)\ ist.

Von „http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Formelsammlung“
Persönliche Werkzeuge