Pseudoprimzahlen: Eulersche Pseudoprimzahlen

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 Primteiler einer 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  .
  1. On the number of false witnesses for a composite number, S. 270 (5.4)