Pseudoprimzahlen: Die konstruierte Pseudoprimzahl

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Pseudoprimzahlen

Die Kunst, eine Pseudoprimzahl nach Maß zu konstruieren[Bearbeiten]

Eine Pseudoprimzahl , die zu irgendeiner natürlichen Zahl pseudoprim, im Sinne des kleinen fermatschen Satz ist, ist recht einfach. Man nehme zwei beliebige, zueinander teilerfremde Primzahlen mit , und multipliziere miteinander. Das Produkt wird dann schon zu wenigstens einer natürlichen Zahl pseudoprim sein. Aber zu welcher Zahl ? Interessant ist es ja, eine Pseudoprimzahl zu erzeugen, die zu einer vorher ausgewählten Zahl pseudoprim ist, ohne sie testen zu müssen.

und müssen zueinander teilerfremd sein[Bearbeiten]

Damit zusammengesetzte Zahl zu einer natürlichen Zahl pseudoprim sein kann, muß immerhin sichergestellt sein, das und zueinander teilerfremd sind. Zu jeder solcher Fermatschen Pseudoprimzahlen der Form lassen sich zwei Basen finden, und zwar durch folgende Vorgehensweise:

Man ermittelt die Vielfachen von und :
und

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 kleine fermatschen Satzes), und sie ist teilerfremd zu und . Es gibt zu jeder Zahl genau zwei Basen die 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 .

Beispiel[Bearbeiten]

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 .