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

Pseudoprimzahlen

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

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

$n$ ausmultipliziert:

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

Faktorisierung:

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

Primfaktoren:

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

Anzahl der teilerfremden Zahlen $\leq n$:

$\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:

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

${\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:

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

Mit

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

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

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

$\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$

Zahlen der Form $n=(12m+1)\cdot (24m+1)$ sind Fermatsche Pseudoprimzahlen zu den Basen 2 und 3 sowie zu Produkten der 2er- und 3er-Potenzen, wenn beide Faktoren Primzahlen sind.

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