Zum Inhalt springen

Pseudoprimzahlen: Pseudoprimzahlen zur Basis a nach Michele Cipolla

Aus Wikibooks

Dieses Kapitel oder dieser Abschnitt ist unverständlich formuliert. Ein Hinweis, was nicht verstanden wird, ist möglicherweise auf der Diskussionsseite des Artikels zu finden. Wenn Sie Hilfe benötigen, schauen Sie, welche Qualitätskriterien an ein gutes Buch gestellt werden. Das allgemeine Vorgehen bei diesem Baustein kannst Du hier nachlesen.

Fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

[Bearbeiten]

Michele Cipolla hat 1904 ein Verfahren zum Erzeugen beliebiger fermatscher Pseudoprimzahlen zu einer beliebigen, natürlichen Basis gefunden. Dazu benötigt man eine Primzahl, die nicht teilt. Warum, das wird weiter unten erklärt.

Mit der Basis und der Primzahl werden zwei Zahlen und erzeugt:

Das Produkt ist eine fermatsche Pseudoprimzahl zur Basis

Erklärung

[Bearbeiten]

Die Bedingung, dass teilerfremd zu sein soll, kann auch so formuliert werden: soll eine Primzahl sein, die nicht teilt, da nach der dritten binomischen Formel ist. Damit ist sichergestellt, dass zu , und teilerfremd ist.

und sind beides Partialsummen geometrischer Reihen, nämlich:

und


Aus und

folgt, dass auch ist.

Aus

folgt, dass ist,

so dass n eine Pseudoprimzahl zur Basis a sein muss. Da es unendlich viele Primzahlen gibt, muss es demnach auch unendlich viele Pseudoprimzahlen zu jeder Basis a geben.

Liste fermatscher Pseudoprimzahlen zur Basis a nach Michele Cipolla

[Bearbeiten]
a p n1 n2 n=n1•n2 Faktoren
2 5 31 11 341 11•31
2 7 127 43 5461 43•127
3 5 121 61 7381 11•11•61
3 7 1093 547 597871 547•1093
2 11 2047 683 1398101 23•89•683
7 5 2801 2101 5884901 11•191•2801
2 13 8191 2731 22369621 2731•8191
5 7 19531 13021 254313151 29•449•19531
13 5 30941 26521 809977861 11•2411•30941
3 11 88573 44287 3922632451 23•67•661•3851
2 17 131071 43691 5726623061 43691•131071
17 5 88741 78881 6999978821 11•71•101•88741
2 19 524287 174763 91625968981 174763•524287
3 13 797161 398581 317733228541 398581•797161
11 7 1948717 1623931 3164581946527 43•45319•1623931
2 23 8388608 2796203 23456248059221 47•178481•2796203