Pseudoprimzahlen: Eulersche Pseudoprimzahlen

Aus Wikibooks

[Bearbeiten] Eulersche Pseudoprimzahl

Um eine eulersche Pseudoprimzahl zu sein, muß eine zusammengesetzte Zahl n wenigstens eine natürliche Zahl a zur Basis haben, für die gilt a > 1, die teilerfremd zu n ist, und für die entweder oder gilt. Diese Zahl nennt man auch eulersche Pseudoprimzahl zur Basis a (EPsP).

[Bearbeiten] Ableitung der der eulerschen Pseudoprimzahl aus der fermatschen Pseudoprimzahl

Ein Beispiel für eine eulersche Pseudoprimzahl zur

Es läßt sich ziemlich einfach, nämlich durch quadrieren, zeigen, das eine eulersche pseudoprimzahl auch eine fermatsche Pseudoprimzahl ist.

und ( − 1)² = 1² = 1

Daraus das eine eulersche Pseudoprimzahl eine eine fermatsche Pseudoprimzahl ist, läßt sich nicht der Umkehrschluß ziehen, das jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das läßt sich anhand der fermatschen Pseudoprimzahl 15 zeigen:

. Die 15 kann also keine eulersche Pseudoprimzahl zur Basis 11 sein. Aber , demzufolge ist 15 eine fermatsche Pseudoprimzahl.