Eine Pseudoprimzahl
, die zu irgendeiner natürlichen Zahl
pseudoprim im Sinne des kleinen fermatschen Satz ist, zu konstruieren, ist recht einfach. Man nehme zwei beliebige Primzahlen
mit
, und multipliziere sie miteinander. Das Produkt wird dann schon zu mindestens einer natürlichen Zahl
pseudoprim sein. Aber zu welcher Zahl
?
und
müssen zueinander teilerfremd sein
Damit eine zusammengesetzte Zahl
zu einer natürlichen Zahl
pseudoprim sein kann, muss immerhin sichergestellt sein, dass
und
zueinander teilerfremd sind.
Zu jeder solchen Fermatschen Pseudoprimzahl der Form
lassen sich zwei Basen
finden, und zwar durch folgende Vorgehensweise:
- Man ermittelt die Vielfachen von
und
:
![{\displaystyle p_{1},\ 2\cdot p_{1},\ 3\cdot p_{1},\ 4\cdot p_{1},\ 5\cdot p_{1},...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e78939bae664d8cc511c5c90b68516937faa75fa)
- und
![{\displaystyle p_{2},\ 2\cdot p_{2},\ 3\cdot p_{2},\ 4\cdot p_{2},\ 5\cdot p_{2},...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a157db612933d0660fbd47383cb4c4115af1ad9c)
Dann sucht man jeweils ein Vielfaches
und
heraus, für die
gilt. Die zwischen
und
liegende Zahl ist eine Basis, zu der die Zahl
pseudoprim ist (im Sinne des kleinen fermatschen Satzes), und sie ist teilerfremd zu
und
.
Es gibt zu jeder Zahl
genau zwei Basen
, die sich auf diese Weise finden lassen und kleiner als
sind. Die Summe dieser beiden Basen
und
ist
. Alle Basen
, die größer als
sind und sich nach dem beschriebenen Algorithmus konstruieren lassen, haben entweder die Form
oder
.
Das Produkt
ist immer pseudoprim zur Basis
, wenn
ist, auch wenn
oder
zusammengesetzt ist.
Beweis:
Die Vielfachen von
sind:
Die Vielfachen von
sind:
Von diesen Vielfachen haben
und
beziehungsweise
und
eine Differenz von
. Die zwischen
und
liegende Zahl
und die zwischen
und
liegende Zahl
sind Basen zu denen die Zahl
pseudoprim ist.
Die Summe von
und
ist
.