Pseudoprimzahlen: Die konstruierte Pseudoprimzahl

Pseudoprimzahlen

Eine Pseudoprimzahl $q\$, die zu irgendeiner natürlichen Zahl $a\$ pseudoprim im Sinne des kleinen fermatschen Satz ist, zu konstruieren, ist recht einfach. Man nehme zwei beliebige Primzahlen $\ p_{i}\$ mit $\ p_{i}\geq 3$, und multipliziere sie miteinander. Das Produkt wird dann schon zu mindestens einer natürlichen Zahl $a\$ pseudoprim sein. Aber zu welcher Zahl $a$?

$a\$ und $\ q\$ müssen zueinander teilerfremd sein

Damit eine zusammengesetzte Zahl $\ q\$ zu einer natürlichen Zahl $a\$ pseudoprim sein kann, muss immerhin sichergestellt sein, dass $a\$ und $q\$ zueinander teilerfremd sind. Zu jeder solchen Fermatschen Pseudoprimzahl der Form $q=p_{1}\cdot p_{2}\$ lassen sich zwei Basen $a\$ finden, und zwar durch folgende Vorgehensweise:

Man ermittelt die Vielfachen von $p_{1}\$ und $p_{2}\$:

$p_{1},\ 2\cdot p_{1},\ 3\cdot p_{1},\ 4\cdot p_{1},\ 5\cdot p_{1},...$

und

$p_{2},\ 2\cdot p_{2},\ 3\cdot p_{2},\ 4\cdot p_{2},\ 5\cdot p_{2},...$

Dann sucht man jeweils ein Vielfaches $m\cdot p_{1}$ und $n\cdot p_{2}$ heraus, für die $|m\cdot p_{1}-n\cdot p_{2}|=2$ gilt. Die zwischen $m\cdot p_{1}$ und $n\cdot p_{2}$ liegende Zahl ist eine Basis, zu der die Zahl $q=p_{1}\cdot p_{2}$ pseudoprim ist (im Sinne des kleinen fermatschen Satzes), und sie ist teilerfremd zu $p_{1},\ p_{2},\ m$ und $n\$. Es gibt zu jeder Zahl $q=p_{1}\cdot p_{2}$ genau zwei Basen $a$, die sich auf diese Weise finden lassen und kleiner als $q\$ sind. Die Summe dieser beiden Basen $\ a_{1}\$ und $\ a_{2}\$ ist $\ q$. Alle Basen $a\$, die größer als $q\$ sind und sich nach dem beschriebenen Algorithmus konstruieren lassen, haben entweder die Form $a=a_{1}+m\cdot q$ oder $a=a_{2}+m\cdot q$.

Das Produkt $(a-1)(a+1)=(a^{2}-1)\$ist immer pseudoprim zur Basis $a$, wenn $a=2k>3$ ist, auch wenn $a+1$ oder $a-1$ zusammengesetzt ist.

Beweis:
${\begin{aligned}a^{(a+1)(a-1)-1}&=a^{a^{2}-2}\\&=a^{(2k)^{2}-2}\\&=(a^{2})^{2k^{2}-1}\\&=((a^{2}-1)+1)^{2k^{2}-1}\\&\equiv 1^{2k^{2}-1}\equiv 1{\pmod {(a^{2}-1)}}\equiv 1{\pmod {((a+1)(a-1))}}\end{aligned}}$

Beispiel

$391=17\cdot 23$

Die Vielfachen von $17\$ sind: $17,\ 34,\ 51,\ 68,\ 85,\ 102,\ 119,\ 136,\ 153,\ 170,\ 187,\ 204,\ 221,\ 238,\ 255,\ 272,\ ...$

Die Vielfachen von $23\$ sind: $23,\ 46,\ 69,\ 92,\ 115,\ 138,\ 161,\ 184,\ 207,\ 230,\ 253,\ 276,\ ...$

Von diesen Vielfachen haben $136\$ und $138\$ beziehungsweise $253\$ und $255\$ eine Differenz von $2\$. Die zwischen $136\$ und $138\$ liegende Zahl $137\$ und die zwischen $253\$ und $255\$ liegende Zahl $254\$ sind Basen zu denen die Zahl $391\$ pseudoprim ist.

Die Summe von $137\$ und $254\$ ist $391\$.