Pseudoprimzahlen: Eulersche Pseudoprimzahlen

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Pseudoprimzahlen

Eulersche Pseudoprimzahl[Bearbeiten]

Eine zusammengesetzte Zahl n ist eine eulersche Pseudoprimzahl, wenn es wenigstens eine natürliche Zahl zur Basis hat, die teilerfremd zu n ist, und für die entweder gilt:

oder

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

Ableitung der eulerschen Pseudoprimzahl aus der fermatschen Pseudoprimzahl[Bearbeiten]

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. 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 das eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl ist, läßt sich nicht der Umkehrschluß ziehen, dass jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das läßt 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.