Zum Inhalt springen

Pseudoprimzahlen: Ein erstes Intermezzo

Aus Wikibooks

Angenommen man hat nur eine ungerade Zahl , von der man weiß, das sie zusammengesetzt und quadratfrei ist. Auf welche Weise kann man dann herausfinden, zu welchen Basen diese Zahl pseudoprim ist, ohne für alle potentielle Basen auf die Beziehung zu testen?

Wenn man die Faktorisierung kennt, ist das relativ einfach. Ein quadratfreies Produkt aus zueinander teilerfremden, ungeraden Primzahlen ist immer eine fermatsche Pseudoprimzahl. Das ist so, weil jede zusammegesetzte ungerade Zahl, mit Ausnahme der 3er-Potenzen (9, 27, 81, 243, ...), eine fermatsche Pseudoprimzahl ist. Aber zu welcher Basis ist die entsprechende zusammengesetzte, ungerade Zahl pseudoprim?

Vielleicht löst sich die Frage für bestimmte Zahlen noch. Hier also ein kleines Spiel:

Man nimmt zwei ungerade Zahlen, und berechnet die Vielfachen. Der Einfachheit werden mal 3 und 7 genommen:
3: 3,  6,  9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, ...
7: 7, 14, 21, 28, 35, 42, 49, 56, 63, ...
Nun sucht man immer zwei Zahlen heraus, die um 2 differieren:
(7, 9) (12, 14) (28, 30) (33, 35) (54, 56) ...

Wenn man aus den Zahlen, die zwischen diesen Zahlenpaaren liegen eine Folge macht bekommt man:

8, 13, 29, 34, 55, ...

Kommt einem diese Zahlenfolge bekannt vor? Wahrscheinlich nicht. So, jetzt bestimmt man die Basen, zu denen die Zahl 21 = 3*7 pseudoprim ist:

21 ist pseudoprim zu?

Wie sieht das bei Quadratfreien Produkten aus mehr als zwei Primzahlen aus?

Beispiel :
 11: 385, 396, 770, 781, 1166, 1177, 1562, 
391: 391, 782, 1173, 1564, 1955, 2346, 2737, 3128, 3519, 1910, 
 17:
253:
 23:
187:
Regeln zur Ableitung von Basen zu einer fermatschen Pseudoprimzahl
  1. Eine fermatsche Pseudoprimzahl ist mindestens zu einer zu teilerfremden Basis mit pseudoprim.
  2. Wenn eine fermatsche Pseudoprimzahl zu einer Basis mit pseudoprim ist, so ist auch pseudoprim zu jeder Basis der Form mit .
  3. Wenn eine fermatsche Pseudoprimzahl zu einer Basis pseudoprim ist, so ist auch pseudoprim zu jeder Basis der Form mit .
  4. Wenn eine fermatsche Pseudoprimzahl zu einer Basis der Form mit pseudoprim ist, so ist auch pseudoprim zu mit
  5. Wenn eine ungerade fermatsche Pseudoprimzahl zu einer Basis mit pseudoprim ist, so ist auch zu der Basis pseudoprim.

Anhand der folgenden Beispiele werden die Regeln 2 bis 7 gezeigt werden:

Beispiel Regel 2.:
Beispiel Regel 3.:
Beispiel Regel 4.:
Beispiel Regel 5.:
15 ist eine fermatsche Pseudoprimzahl, die u.a. zur Basis 11 pseudoprim ist. Nach Regel 4. ist auch eine Basis zu der 15 Pseudoprim ist.

Wenn man davon ausgeht, das auch zusammengesetzte Zahlen existieren, die keine fermatschen Pseudoprimzahlen sind, und damit auch keine eulerschen oder starken Pseudoprimzahlen, so muß man berücksichtigen, das es zwei Regeln gibt, die für alle Zahlen gelten, seien es nun Primzahlen, fermatsche Pseudoprimzahlen oder auch solche, die weder das eine noch das andere sind.

Keine Kriterien für fermatsche Pseudoprimzahlen
  1. Für jede ungerade Zahl mit gilt: mit
  2. Für jede natürliche Zahl mit gilt: mit