Pseudoprimzahlen: Eulersche Pseudoprimzahlen

Aus Wikibooks

Für jede ungerade Primzahl gilt mit jeder teilerfremden Basis die Kongruenz

.  

Dabei bezeichnet das Jacobi-Symbol.

Eulersche Pseudoprimzahl[Bearbeiten]

Eine zusammengesetzte Zahl n ist eine eulersche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl im Bereich als Basis gibt, mit der entweder

(1a)

oder

(1b)

ist.

Eine solche Zahl nennt man eulersche Pseudoprimzahl zur Basis a, kurz: EPsP(a).

Eulersche Pseudoprimzahlen sind auch Fermatsche Pseudoprimzahlen[Bearbeiten]

Es lässt sich ziemlich einfach, nämlich durch Quadrieren, zeigen, dass jede eulersche Pseudoprimzahl auch eine fermatsche Pseudoprimzahl ist. Es sei n eine eulersche Pseudoprimzahl zur Basis a. Es gilt also:

Folglich ist:

und deshalb ist n auch eine fermatsche Pseudoprimzahl zur Basis a.

Daraus dass eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl ist, lässt sich nicht der Umkehrschluss ziehen, dass jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das lässt sich anhand der fermatschen Pseudoprimzahl 15 zeigen:

.

Die Zahl 15 ist also keine eulersche Pseudoprimzahl zur Basis 11. Aber

demzufolge ist 15 eine fermatsche Pseudoprimzahl zur Basis 11.

Euler-Jacobi-Pseudoprimzahl[Bearbeiten]

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

(2)

ist.

Euler-Jacobi-Pseudoprimzahlen werden oft auch "Eulersche Pseudoprimzahlen" genannt.

Da der Wert des Jacobi-Symbols mit teilerfremden Parametern nur 1 oder -1 sein kann, ist jede Euler-Jacobi-Pseudoprimzahl auch eine eulersche Pseudoprimzahl;

  • für 1 gilt Kongruenz 1a,
  • für -1 gilt 1b.

Anzahl der Basen[Bearbeiten]

Wenn die Primteilereiner zusammengesetzten Zahl bekannt sind, kann die Anzahl der Basen, zu denen sie Euler-Jacobi-Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

 

ist die Anzahl der Basen einschließlich 1 und n-1

[1]  

Dabei ist

  • der größte Exponent, mit dem gilt,, so dass ist,
  • der größte ungerade Teiler von ,
  • der größte Exponent, mit dem gilt, so dass ist und
  • das Minimum aller .

Quellen[Bearbeiten]

  1. On the number of false witnesses for a composite number, S. 270 (5.4)