Pseudoprimzahlen: Eulersche Pseudoprimzahlen

Für jede ungerade Primzahl ${\displaystyle p}$ gilt mit jeder teilerfremden Basis ${\displaystyle a}$ die Kongruenz

${\displaystyle a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right)=\pm 1{\pmod {n}}}$.

Dabei bezeichnet ${\displaystyle \left({\frac {a}{n}}\right)}$ das Jacobi-Symbol.

Eine zusammengesetzte Zahl n ist eine eulersche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl ${\displaystyle a}$ im Bereich ${\displaystyle 1<a<n-1}$ als Basis gibt, mit der entweder

${\displaystyle a^{\frac {n-1}{2}}\equiv 1{\pmod {n}}}$

(1a)

oder

${\displaystyle a^{\frac {n-1}{2}}\equiv -1{\pmod {n}}}$

(1b)

ist.

Eine solche Zahl nennt man eulersche Pseudoprimzahl zur Basis a, kurz: EPsP(a).

Es lässt sich ziemlich einfach, nämlich durch Quadrieren, zeigen, dass jede eulersche Pseudoprimzahl auch eine fermatsche Pseudoprimzahl ist. Es sei n eine eulersche Pseudoprimzahl zur Basis a. Es gilt also:

${\displaystyle a^{\frac {n-1}{2}}\equiv \pm 1{\pmod {n}}.}$

Folglich ist:

${\displaystyle a^{n-1}=\left(a^{\frac {n-1}{2}}\right)^{2}\equiv (\pm 1)^{2}=1{\pmod {n}},}$

und deshalb ist n auch eine fermatsche Pseudoprimzahl zur Basis a.

Daraus dass eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl ist, lässt sich nicht der Umkehrschluss ziehen, dass jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das lässt sich anhand der fermatschen Pseudoprimzahl 15 zeigen:

${\displaystyle 11^{7}\equiv 11{\pmod {15}}}$.

Die Zahl 15 ist also keine eulersche Pseudoprimzahl zur Basis 11. Aber

${\displaystyle 11^{14}\equiv 1{\pmod {15}},}$

demzufolge ist 15 eine fermatsche Pseudoprimzahl zur Basis 11.

Eine ungerade zusammengesetzte natürliche Zahl ${\displaystyle n}$ heißt Euler-Jacobi-Pseudoprimzahl zur Basis a, wenn ${\displaystyle n}$ und ${\displaystyle a}$ teilerfremd sind und

${\displaystyle a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$

(2)

ist.

Euler-Jacobi-Pseudoprimzahlen werden oft auch "Eulersche Pseudoprimzahlen" genannt.

Da der Wert des Jacobi-Symbols mit teilerfremden Parametern nur 1 oder -1 sein kann, ist jede Euler-Jacobi-Pseudoprimzahl auch eine eulersche Pseudoprimzahl;

• für 1 gilt Kongruenz 1a,
• für -1 gilt 1b.

Wenn die Primteiler${\displaystyle \ p_{i}\ }$einer zusammengesetzten Zahl ${\displaystyle n}$ bekannt sind, kann die Anzahl der Basen, zu denen sie Euler-Jacobi-Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

${\displaystyle n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}{\text{ und }}\ n-1=d\cdot 2^{s}{\text{ mit }}d{\text{ ungerade }}}$

ist die Anzahl der Basen ${\displaystyle <n}$ einschließlich 1 und n-1

${\displaystyle \prod _{i=1}^{k}\gcd \left({\frac {n-1}{2}},\ p_{i}^{'}\right)\cdot {\begin{cases}2&{\text{wenn }}\nu =s\\1/2&{\text{wenn }}\exists \ p_{i}{\text{ mit }}\nu _{2}(p_{i})<s{\text{ und }}\alpha _{i}{\text{ ungerade}}\\1&{\text{sonst }}\end{cases}}}$[1]

Dabei ist

• ${\displaystyle \ s}$ der größte Exponent, mit dem ${\displaystyle \ 2^{s}|n-1\ }$gilt,, so dass ${\displaystyle \ n-1=d\cdot 2^{s}\ }$ist,
• ${\displaystyle \ p_{i}^{'}}$ der größte ungerade Teiler von ${\displaystyle \ p_{i}-1}$,
• ${\displaystyle \ \nu _{2}(p_{i})}$ der größte Exponent, mit dem ${\displaystyle \ 2^{\nu _{2}(p_{i})}|p_{i}-1\ }$gilt, so dass ${\displaystyle \ p_{i}-1=2^{\nu _{2}(p_{i})}\cdot p_{i}^{'}\ }$ist und
• ${\displaystyle \ \nu }$ das Minimum aller ${\displaystyle \nu _{2}(p_{i})}$.

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