Pseudoprimzahlen: Ein erstes Intermezzo

Pseudoprimzahlen

A

Angenommen man hat nur eine ungerade Zahl $n\$, 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 $a^{n-1}\equiv 1\mod n$ 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 $4301=11\cdot 17\cdot 23$:

 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

Eine fermatsche Pseudoprimzahl $q\$ ist mindestens zu einer zu $q\$ teilerfremden Basis $a\$ mit $2\leq a\leq q-2$ pseudoprim. Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ mit $a<q\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu jeder Basis der Form $a+n\cdot q$ mit $n\geq 1\$. Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu jeder Basis der Form $a^{n}\$ mit $n\geq 1\$. Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis der Form $a^{n}\$ mit $n\geq 1\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu $a^{n}\mod q\$ mit $n\geq 1\$ Wenn eine ungerade fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ mit $a<q\$ pseudoprim ist, so ist $q\$ auch zu der Basis $(q-a)\$ 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 $15-11=4$ 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
Für jede ungerade Zahl $n\$ mit $n\geq 3\$ gilt: $\left((n-1)+n\cdot m\right)^{n-1}\equiv 1{\pmod {n}}$ mit $m\geq 0$ Für jede natürliche Zahl $n\$ mit $n\geq 2\$ gilt: $(1+n\cdot m)^{n-1}\equiv 1{\pmod {n}}$ mit $m\geq 0$