Pseudoprimzahlen: (6m+1)(12m+1)

Zahlen der Form ${\displaystyle n=(6m+1)\cdot (12m+1)}$ sind zu besonders vielen Basen pseudoprim.

Wenn ${\displaystyle m>0}$ und ungerade ist, und beide Faktoren Primzahlen sind, ist n Fermatsche Pseudoprimzahl zu ${\displaystyle \varphi (n)/2}$ Basen und starke Pseudoprimzahl zu ${\displaystyle \varphi (n)/4}$ Basen; letzteres ist der maximal mögliche Anteil falscher Zeugen.

${\displaystyle n}$ ausmultipliziert:

${\displaystyle n=(6m+1)\cdot (12m+1)=72m^{2}+18m+1}$

Faktorisierung:

${\displaystyle n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}},\quad k=2,\quad \alpha _{i}=1\quad \forall \ 1\leq i\leq 2}$

Primfaktoren:

${\displaystyle p_{1}=6m+1,\quad p_{2}=12m+1}$

Anzahl der teilerfremden Zahlen ${\displaystyle \leq n}$:

${\displaystyle \varphi (n)=\prod _{i=1}^{k}p_{i}^{\alpha _{i}-1}(p_{i}-1)=\prod _{i=1}^{2}(p_{i}-1)=(6m)\cdot (12m)=72m^{2}}$

(Eulersche φ-Funktion)

Anzahl der Basen für Fermatsche Pseudoprimzahlen:

${\displaystyle \prod _{i=1}^{k}\gcd(n-1,p_{i}-1)}$[1]

${\displaystyle {\begin{aligned}\prod _{i=1}^{k}\gcd(n-1,p_{i}-1)&=\gcd(72m^{2}+18m,6m)\cdot \gcd(72m^{2}+18m,12m)\\&=(6m)\cdot (6m)=36m^{2}=\varphi (n)/2\end{aligned}}}$

Anzahl der Basen für starke Pseudoprimzahlen:

${\displaystyle \left(1+{\frac {2^{k\nu }-1}{2^{k}-1}}\right)\prod _{i=1}^{k}\gcd \left(d,\ p_{i}^{'}\right)}$[2]

Mit

${\displaystyle d=36m^{2}+9m}$,

${\displaystyle p_{1}-1=6m,\ p_{2}-1=12m\quad \Rightarrow \quad p_{1}^{'}=p_{2}^{'}=3m\ }$ und

${\displaystyle \nu =\nu _{2}(p_{1})=1\ }$ ist

${\displaystyle \left(1+{\frac {2^{k\nu }-1}{2^{k}-1}}\right)\prod _{i=1}^{k}\gcd \left(d,\ p_{i}^{'}\right)=2\cdot \prod _{i=1}^{2}\gcd \left(36m^{2}+9m,3m\right)=18m^{2}=\varphi (n)/4}$

Wenn ${\displaystyle m}$ gerade ist, und beide Faktoren Primzahlen sind, ist ${\displaystyle n}$ Fermatsche Pseudoprimzahl zu den Basen 2 und 3 sowie zu Produkten der 2er- und 3er-Potenzen. Der Anteil der Basen ist dann geringer als für ungerade ${\displaystyle m}$.

Beispiel: ${\displaystyle 2701=(6\cdot 6+1)\cdot (12\cdot 6+1)=37\cdot 73}$ ist die kleinste derartige Zahl und zu 2, 3, 4, 6, 8, 9, 12, 16, 18, ... pseudoprim.

1. ↑ Lucas Pseudoprimes
2. ↑ On the number of false witnesses for a composite number, S. 270 (5.4)