Pseudoprimzahlen: Pseudoprimzahlen zur Basis a nach Michele Cipolla

Aus Wikibooks

Wechseln zu: Navigation, Suche

[Bearbeiten] fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

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

Mit der Basis a\ und der Primzahl p\ werden zwei Zahlen n_1\ und n_2\ erzeugt:

n_1=\frac{a^p-1}{a-1} \ \ n_2=\frac{a^p+1}{a+1}

Das Produkt n = n_1\cdot n_2\ ist eine fermatsche Pseudoprimzahl zur Basis a\

[Bearbeiten] Erklärung

Die Bedingung, das p\ teilerfremd zu a(a^2-1)\ sein soll, kann auch so formuliert werden: p\ soll eine Primzahl sein, die (a-1)\cdot a\cdot(a+1)\ nicht teilt. (a^2-1)\ ist nichts anderes als die dritte Binomische Formel: (a^2-1) = (a-1)\cdot (a+1)\ . Damit ist sichergestellt, das p\ zu a\ , (a-1)\ und (a+1)\ teilerfremd ist.

\frac{a^p-1}{a-1} und \frac{a^p+1}{a+1} sind beides geometrische Reihen, nämlich:

\frac{a^p-1}{a-1} = a^{p-1} + a^{p-2} + ... + a^2 + a + 1 und \frac{a^p+1}{a+1} =


Aus n_1 \equiv 1 \mod 2p und n_2 \equiv 1 \mod 2p

folgt, dass auch n \equiv 1 \mod 2p ist.

Aus a^{2p} \equiv 1 \mod n

folgt, dass a^{n-1} \equiv 1 \mod n ist,

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

[Bearbeiten] eine Liste fermatscher Pseudoprimzahlen zur zur Basis a nach Michele Cipolla

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
Von „http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Pseudoprimzahlen_zur_Basis_a_nach_Michele_Cipolla“
Persönliche Werkzeuge