Pseudoprimzahlen: Pseudoprimzahlen zur Basis a nach Michele Cipolla

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$

Erklärung

Die Bedingung, dass $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, da nach der dritten binomischen Formel $(a^2-1)=(a-1)\cdot (a+1)$ ist. Damit ist sichergestellt, dass $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 Partialsummen geometrischer 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}=(-a{)}^{p-1}+(-a{)}^{p-2}+...+(-a{)}^2+(-a)+1$

Aus $n_1\equiv 1mod2p$ und $n_2\equiv 1mod2p$

folgt, dass auch $n\equiv 1mod2p$ ist.

Aus $a^{2p}\equiv 1modn$

folgt, dass $a^{n-1}\equiv 1modn$ 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

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