Zum Inhalt springen

Pseudoprimzahlen: Schnellübersicht

Aus Wikibooks

Schnellübersicht

[Bearbeiten]

Hier werden die wichtigen Dinge und Fragen kurz abgehandelt.

Was sind Pseudoprimzahlen?

  • Pseudoprimzahlen sind zusammengesetzte Zahlen (d.h. Nichtprimzahlen), die Eigenschaften haben, die normalerweise nur Primzahlen haben.
Fermatsche Pseudoprimzahlen
[Bearbeiten]

Was sind fermatsche Pseudoprimzahlen?

  • Fermatsche Pseudoprimzahlen sind zusammengesetzte Zahlen, die in Bezug auf den kleinen fermatschen Satz für bestimmte Basen Primzahlen gleichen!

Warum reicht es, eine zusammengesetzte Zahl auf zu testen, statt auf ?

  • Weil für jede ungerade natürliche Zahl gilt, wenn ist.

Welche zusammengesetzten, ungeraden Zahlen sind keine fermatschen Pseudoprimzahlen?

  • Keine der Dreierpotenzen mit ist eine fermatsche Pseudoprimzahl!

Warum ist es nicht unbedingt notwendig, zusammengesetzte Zahlen auf Basen zu testen?

  • Alle Basen lassen sich als mit darstellen. Mit anderen Worten: Wenn es keine Basis mit gibt, zu der pseudoprim ist, so gibt es gar keine Basis , zu der pseudoprim ist!