Pseudoprimzahlen: Die konstruierte Pseudoprimzahl

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\ge 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{array}{cc}{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(\mathrm{mod}(a^2-1))\equiv 1(\mathrm{mod}((a+1)(a-1)))\end{array}$

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$.