Pseudoprimzahlen: Eulersche Pseudoprimzahlen
Für jede ungerade Primzahl gilt mit jeder teilerfremden Basis die Kongruenz
. |
Dabei bezeichnet das Jacobi-Symbol.
Eulersche Pseudoprimzahl
BearbeitenEine 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
BearbeitenEs 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
BearbeitenEine 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;
Anzahl der Basen
BearbeitenWenn 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 .
Quellen
Bearbeiten