Eulersche Pseudoprimzahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz

erfüllt ist.

Anders ausgedrückt muss n die Differenz oder die Summe teilen.

Eine Folgerung aus dem kleinen fermatschen Satz[Bearbeiten | Quelltext bearbeiten]

Eine eulersche Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf eine Folgerung aus dem kleinen Fermatschen Satz:

ist p eine ungerade Primzahl, so teilt sie , also auch einen der beiden Faktoren (dritte Binomische Formel). Beispielsweise ist 7 ein Teiler von 36-1 = 728 = 26·28, und einer der Faktoren ist durch 7 teilbar. Dieses Kriterium lässt sich für Primzahltests verwenden. Wie üblich nennt man die zusammengesetzten Zahlen, die das Kriterium erfüllen, Pseudoprimzahlen (in Bezug auf die betrachtete Eigenschaft).

Jede eulersche Pseudoprimzahl ist eine fermatsche Pseudoprimzahl (man quadriere beide Seiten der Kongruenz). Sie sind nach Leonhard Euler benannt.

Definition[Bearbeiten | Quelltext bearbeiten]

Es gibt zwei Varianten, den Begriff eulersche Pseudoprimzahl zu definieren. Beide Fälle setzen voraus, dass die Basis a teilerfremd zu n ist.

Eulersche Pseudoprimzahl[Bearbeiten | Quelltext bearbeiten]

Eine ungerade zusammengesetzte natürliche Zahl heißt eulersche Pseudoprimzahl zur Basis a, wenn

gilt.[1]

Euler-Jacobi-Pseudoprimzahl[Bearbeiten | Quelltext bearbeiten]

Eine ungerade zusammengesetzte natürliche Zahl heißt Euler-Jacobi-Pseudoprimzahl zur Basis a, wenn

gilt. Dabei bezeichnet das Jacobi-Symbol.[2]
Für prime n wird diese Eigenschaft eulersches Kriterium (für das Legendre-Symbol) genannt; es gilt nämlich für alle Primzahlen p > 2:

.

Vergleich[Bearbeiten | Quelltext bearbeiten]

Offenbar impliziert die zweite Variante die erste (da für teilerfremde a und n das Jacobi-Symbol die Werte +1 und -1 annimmt). Die Beispiele n = 341, a = 2 oder n = 21, a = 8 zeigen, dass die Umkehrung falsch ist. Die zweite Definition ist also echt stärker. Das Vorgehen der zweiten Definition ist die Basis des Solovay-Strassen-Tests.

Eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist[Bearbeiten | Quelltext bearbeiten]

Die Zahl n = 15 liefert mit der Basis a = 11 ein Beispiel für eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist:

Es gilt:

,

aber

 ;

Man beachte:

.

Absolute eulersche Pseudoprimzahlen[Bearbeiten | Quelltext bearbeiten]

Zahlen, die zu allen teilerfremden Basen eine eulersche Pseudoprimzahl darstellen, nennt man absolute eulersche Pseudoprimzahlen.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Neil Koblitz: A Course in Number Theory and Cryptography. 2nd edition. Springer, New York NY u. a. 1994, ISBN 3-540-96576-9 (Graduate Texts in Mathematics 114).

sowie die in Pseudoprimzahl angegebene Literatur.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Eric W. Weisstein: "Euler Pseudoprime." (MathWorld)
  2. Eric W. Weisstein: "Euler-Jacobi Pseudoprime." (MathWorld)