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
erfüllt ist.
Anders ausgedrückt muss n die Differenz oder die Summe teilen.
Eine Folgerung aus dem kleinen fermatschen Satz Bearbeiten
Eine eulersche Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf eine Folgerung aus dem kleinen Fermatschen Satz:
ist p eine ungerade Primzahl, so teilt sie , also auch einen der beiden Faktoren (dritte Binomische Formel). Beispielsweise ist 7 ein Teiler von , 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 Bearbeiten
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 Bearbeiten
Eine ungerade zusammengesetzte natürliche Zahl heißt eulersche Pseudoprimzahl zur Basis a, wenn
gilt.
Euler-Jacobi-Pseudoprimzahl Bearbeiten
Eine ungerade zusammengesetzte natürliche Zahl heißt Euler-Jacobi-Pseudoprimzahl zur Basis a, wenn
gilt. Dabei bezeichnet das Jacobi-Symbol.
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:
Vergleich Bearbeiten
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 Bearbeiten
Die Zahl n = 15 liefert mit der Basis a = 11 ein Beispiel für eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist:
Es gilt:
aber
Man beachte:
Tabelle mit eulerschen Pseudoprimzahlen Bearbeiten
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 und somit nicht teilerfremd ist. Ebenso ist und deswegen kommt 1729 in der Zeile mit Basis a=7 nicht vor. Wegen kommt 2465 in der Zeile mit Basis a=10 nicht vor. Diese besonderen eulerschen Pseudoprimzahlen werden im nächsten Abschnitt behandelt.
Absolute eulersche Pseudoprimzahlen Bearbeiten
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:
Tabelle mit Euler-Jacobi-Pseudoprimzahlen Bearbeiten
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 sind, sind die folgenden:
Das heißt zum Beispiel, dass es 375 Euler-Jacobi-Pseudoprimzahlen zur Basis a = 2 gibt, die kleiner als sind, weil 375 die siebente Zahl in obiger Folge ist.
Zusammenfassung Bearbeiten
- 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:
Literatur Bearbeiten
- 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.