Pseudoprimzahlen: Starke Pseudoprimzahlen

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

die starke Pseudoprimzahl[Bearbeiten]

Um eine starke Pseudoprimzahl zu sein, muß eine zusammengesetzte Zahl nur eine natürliche Zahl a zur Basis haben, für die entweder oder mit gilt.

Um zu zeigen, wie unterschiedlich starke Pseudoprimzahlen ausfallen können, werden als Beispiele die drei Zahlen 781, 1541 und 25 gezeigt. An der Zahl 781 zeigen wird erstmal die Zerlegung gezeigt:

Zerlegung[Bearbeiten]

Gesucht wird das zu einer Zahl zu der Formel . Die Formel können wir Umstellen:

Am Beispiel der Zahl 781 sieht das so aus: Die Primfaktorzerlegung von . Wenn man die 2er-Potenzen entfernt, bleibt für das übrig.

781 zur Basis 5[Bearbeiten]

also ist 781 eine starke Pseudoprimzahl zur Basis 5

1541 zur Basis 5[Bearbeiten]

also ist 1541 eine starke Pseudoprimzahl zur Basis 5

25 zur Basis 7[Bearbeiten]

also ist 25 eine starke Pseudoprimzahl zur Basis 7

305 zur Basis 11[Bearbeiten]

Dies ist ein Gegenbeispiel.

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11

starke Pseudoprimzahl und eulersche Pseudoprimzahl[Bearbeiten]

Damit eine zusammengesetzte natürliche Zahl eine starke Pseudoprimzahl zur Basis sein kann, muß sie auch eine eulersche Pseudoprimzahl zur Basis sein. Warum? Für eine eulersche Pseudoprimzahl zur Basis gilt oder es gilt .

läßt sich auch als schreiben. Wenn nun für zur Basis nun gilt, gilt auch und damit auch .