Eulersche Pseudoprimzahl

Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz

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

erfüllt ist.

Anders ausgedrückt muss n die Differenz ${\displaystyle a^{\frac {n-1}{2}}-1}$ oder die Summe ${\displaystyle a^{\frac {n-1}{2}}+1}$ teilen.

Eine Folgerung aus dem kleinen fermatschen Satz

Eine eulersche Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf eine Folgerung aus dem kleinen Fermatschen Satz:

ist p eine ungerade Primzahl, so teilt sie ${\displaystyle a^{p-1}-1}$, also auch einen der beiden Faktoren ${\displaystyle (a^{\frac {p-1}{2}}+1)(a^{\frac {p-1}{2}}-1)}$ (dritte Binomische Formel). Beispielsweise ist 7 ein Teiler von ${\displaystyle 3^{6}-1=728=2^{3}\cdot 7\cdot 13}$, und einer der Faktoren ist durch 7 teilbar. Dieses Kriterium lässt sich für Primzahltests verwenden. Wie üblich nennt man die zusammengesetzten Zahlen, die das Kriterium erfüllen, Pseudoprimzahlen (in Bezug auf die betrachtete Eigenschaft).

Jede eulersche Pseudoprimzahl ist eine fermatsche Pseudoprimzahl (man quadriere beide Seiten der Kongruenz). Sie sind nach Leonhard Euler benannt.

Definition

Es gibt zwei Varianten, den Begriff eulersche Pseudoprimzahl zu definieren. Beide Fälle setzen voraus, dass die Basis a teilerfremd zu n ist.

Eulersche Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl ${\displaystyle n}$ heißt eulersche Pseudoprimzahl zur Basis a, wenn

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

gilt.^[1]

Euler-Jacobi-Pseudoprimzahl

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

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

gilt. Dabei bezeichnet ${\displaystyle \left({\frac {a}{n}}\right)}$ das Jacobi-Symbol.^[2]
Für prime n wird diese Eigenschaft eulersches Kriterium (für das Legendre-Symbol) genannt; es gilt nämlich für alle Primzahlen p > 2:

${\displaystyle a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right)\mod p}$ .

Vergleich

Offenbar impliziert die zweite Variante die erste (da für teilerfremde a und n das Jacobi-Symbol die Werte +1 und −1 annimmt). Die Beispiele n = 341, a = 2 oder n = 21, a = 8 zeigen, dass die Umkehrung falsch ist. Die zweite Definition ist also echt stärker. Das Vorgehen der zweiten Definition ist die Basis des Solovay-Strassen-Tests.

Eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist

Die Zahl n = 15 liefert mit der Basis a = 11 ein Beispiel für eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist:

Es gilt:

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

aber

${\displaystyle 11^{7}\equiv 11\mod 15}$ ;

Man beachte:

${\displaystyle 11^{2}=121\equiv 1\mod 15}$ .

Tabelle mit eulerschen Pseudoprimzahlen

Es folgt eine Tabelle der kleinsten eulerschen Pseudoprimzahlen (zumindest kleiner gleich 10000) zur Basis a:

a	eulersche Pseudoprimzahlen n zur Basis a	OEIS-Folge
1	9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, … (jede ungerade zusammengesetzte ganze Zahl)
2	341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, 10261, …	(Folge A006970 in OEIS)
3	121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911, 10585, …	(Folge A262051 in OEIS)
4	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, …
5	217, 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, 11041, …	(Folge A262052 in OEIS)
6	185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, 10585, …	(Folge A262053 in OEIS)
7	25, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321, 10225, …	(Folge A262054 in OEIS)
8	9, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709, 10261, …	(Folge A262055 in OEIS)
9	91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, …
10	9, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401, …
11	133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113, …
…	…

Die fett gedruckten Zahlen 1729 und 2465 sind eulersche Pseudoprimzahlen zu allen teilerfremden Basen a. In der Zeile mit Basis a=5 kommt 2465 somit nicht vor, weil ${\displaystyle \operatorname {ggT} (5,2465)=5\not =1}$ und somit nicht teilerfremd ist. Ebenso ist ${\displaystyle \operatorname {ggT} (7,1729)=7\not =1}$ und deswegen kommt 1729 in der Zeile mit Basis a=7 nicht vor. Wegen ${\displaystyle \operatorname {ggT} (10,2465)=5\not =1}$ kommt 2465 in der Zeile mit Basis a=10 nicht vor. Diese besonderen eulerschen Pseudoprimzahlen werden im nächsten Abschnitt behandelt.

Absolute eulersche Pseudoprimzahlen

Zahlen n, die zu allen teilerfremden Basen a eine eulersche Pseudoprimzahl darstellen, nennt man absolute eulersche Pseudoprimzahlen. Die ersten absoluten eulerschen Pseudoprimzahlen sind die folgenden:

1729, 2465, 15841, 41041, 46657, 75361, 162401, 172081, 399001, 449065, 488881, 530881, 656601, 670033, 838201, 997633, … (Folge A033181 in OEIS)

Tabelle mit Euler-Jacobi-Pseudoprimzahlen

Es folgt eine Tabelle der kleinsten Euler-Jacobi-Pseudoprimzahlen (zumindest kleiner gleich 10000) zur Basis a. Alle diese Zahlen kommen schon in der vorhergehenden Tabelle der eulerschen Pseudoprimzahlen vor, weil die Definition der Euler-Jacobi-Pseudoprimzahlen stärker ist als die Definition der eulerschen Pseudoprimzahlen. Jede Euler-Jacobi-Pseudoprimzahl ist auch eulersche Pseudoprimzahl (die Umkehrung gilt nicht):

a	Euler-Jacobi-Pseudoprimzahlen n zur Basis a	OEIS-Folge
1	9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, … (jede ungerade zusammengesetzte ganze Zahl)
2	561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, …	(Folge A047713 in OEIS)
3	121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, …	(Folge A48950 in OEIS)
4	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, …
5	781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, 11041, …
6	217, 481, 1111, 1261, 1729, 2701, 3589, 3913, 5713, 6533, 10585, …
7	25, 325, 703, 2101, 2353, 2465, 3277, 4525, 11041, …
8	9, 65, 105, 273, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 6305, 6601, 7161, 8321, 8481, 9265, 10585, …
9	91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, …
10	9, 91, 481, 1729, 4187, 6533, 6601, 8149, 8401, 10001, 11111, …
11	133, 793, 2047, 2465, 4577, 4921, 5041, 5185, 12403, …
…	…

Im Gegensatz zu den eulerschen Pseudoprimzahlen gibt es keine Zahlen, die Euler-Jacobi-Pseudoprimzahlen zu allen teilerfremden Basen a sind.

Die Anzahl der Euler-Jacobi-Pseudoprimzahlen zur Basis a = 2, die kleiner als ${\displaystyle 10^{n}}$ sind, sind die folgenden:

0, 0, 1, 12, 36, 114, 375, 1071, 2939, 7706, 20417, 53332, 124882 (Folge A55551 in OEIS)

Das heißt zum Beispiel, dass es 375 Euler-Jacobi-Pseudoprimzahlen zur Basis a = 2 gibt, die kleiner als ${\displaystyle 10^{7}}$ sind, weil 375 die siebente Zahl in obiger Folge ist.

Zusammenfassung

• Jede Euler-Jacobi-Pseudoprimzahl zur Basis a ist auch gleichzeitig eine eulersche Pseudoprimzahl zur Basis a. Die Umkehrung gilt nicht, das heißt, es gibt eulersche Pseudoprimzahlen zur Basis a, die nicht gleichzeitig Euler-Jacobi-Pseudoprimzahlen zur Basis a sind.
• Jede eulersche Pseudoprimzahl zur Basis a ist auch eine fermatsche Pseudoprimzahl zur Basis a. Die Umkehrung gilt nicht, das heißt, es gibt fermatsche Pseudoprimzahlen zur Basis a, die nicht gleichzeitig eulersche Pseudoprimzahlen zur Basis a sind.
• Jede Euler-Jacobi-Pseudoprimzahl zur Basis a ist auch gleichzeitig eine fermatsche Pseudoprimzahl zur Basis a. Die Umkehrung gilt nicht, das heißt, es gibt fermatsche Pseudoprimzahlen zur Basis a, die nicht gleichzeitig Euler-Jacobi-Pseudoprimzahlen zur Basis a sind.

Mathematisch mittels Mengenschreibweise formuliert man den obigen Sachverhalt wie folgt:

Euler-Jacobi-Pseudoprimzahl ${\displaystyle \subsetneqq }$ Eulersche Pseudoprimzahl ${\displaystyle \subsetneqq }$ Fermatsche Pseudoprimzahl

Literatur

• Neil Koblitz: A Course in Number Theory and Cryptography. 2nd edition. Springer, New York NY u. a. 1994, ISBN 3-540-96576-9 (Graduate Texts in Mathematics 114).
• Paul Erdős und Carl Pomerance: On the Number of False Witnesses for a Composite Number. Mathematics of Computation 46, 259–279, 1986.
• Carl Pomerance: The Search for Prime Numbers. Scientific American 12/1982.
  Deutsche Übersetzung: Primzahlen im Schnelltest. Spektrum der Wissenschaft 02/1983. Mit Foto eines Nachbaus von Lehmers Fahrradkettencomputer von 1926.
• Carl Pomerance: Computational Number Theory. In: Timothy Gowers (Hrsg.): The Princeton companion to mathematics. S. 348–362, Princeton University Press, 2008 (online; PDF; 249 kB).
• Paulo Ribenboim: The New Book of Prime Number Records. Springer-Verlag, 1996.

Siehe auch

• Starke Pseudoprimzahl
• Super-Eulersche Pseudoprimzahl

Weblinks

• Modulo-Rechner online

Einzelnachweise

1. ↑ Eric W. Weisstein: "Euler Pseudoprime." (MathWorld)
2. ↑ Eric W. Weisstein: "Euler-Jacobi Pseudoprime." (MathWorld)