Pseudoprimzahlen: Spielereien

Aus Wikibooks
Zur Navigation springen Zur Suche springen
  • Ich kenne von einer Pseudoprimzahl nur die Primzahlbasen zu denen die Pseudoprimzahl pseudoprim ist, möchte aber alle Basen bekommen, zu denen die Pseudoprimzahl pseudoprim ist, ohne jede natürliche Zahl zu testen.

Beispiel 65:

die Primzahlbasen (a<65) zur Pseudoprimzahl 65 sind 31, 47 und 53.

Demzufolge ist 65 auch zu allen Potenzen dieser Primzahlen pseudoprim:

n 31 mod 65 47 mod 65 53 mod 65
2 961 51 2209 64 2809 14
3 29791 21 103823 18 148877 27
4 923521 1 4789681 1 7890481 1

Damit haben wir als Basen (a<65), zu denen die Pseudoprimzahl 65 pseudoprim ist, die Zahlen 14, 18, 21, 27, 31, 47, 51, 53 und 64. Jetzt fehlen noch die Basen der Form (65 - a):

65 - 53 = 12; 65 - 51 = 14; 65 - 47 = 18; 65 - 31 = 34; 65 - 27 = 38; 65 - 21 = 44; 65 - 18 = 47; 65 - 14 = 51.

Nun haben wir alle Basen a mit a<65, zu denen die 65 Pseudoprim ist: 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53 und 64.

Halt: es fehlen noch 8 und 57.