Fermatsche Pseudoprimzahlen

Eine Fermatsche Pseudoprimzahl ist eine zusammengesetzte, natürliche Zahl nn, zu der mindestens eine natürliche Zahl aa mit ggT⁡(a,n)=1\ggT(a,n) = 1 und a>1a > 1 existiert, so das:
an−1≡1mod  na^{n-1} \equiv 1 \mod n, gilt.(1)
Man sagt zu diesen Zahlen auch: "nn ist pseudoprim zur Basis aa".
Die Gültigkeit der Beziehung (1) suggeriert auf Grund des kleinen Fermatschen Satzes, dass es sich bei nn um eine Primzahl handeln könnte, da dieser für Primzahlen gilt, womit natürlich nicht gesagt ist, dass er für zusammengesetzte Zahlen nicht gilt.

Beispiel

Für die Zahl 91=7⋅1391=7\cdot 13 gilt:
17 1790−117^{90}-1 ist durch 91 teilbar
29 2990−129^{90}-1 ist durch 91 teilbar
61 6190−161^{90}-1 ist durch 91 teilbar
Obwohl die 91 für bestimmte aa (3, 17, 23, 29, 43, 53, 61 und 79) den kleinen Fermatschen Satz erfüllt, ist sie keine Primzahl.

Die kleinsten fermatschen Pseudoprimzahlen zu bestimmten Primbasen

kleinste Pseudoprimzahl zu den Basen
4 5
15 11
21 13
91 3
341 2
2701 2, 3
29341 2, 3, 5, 7, 11
162401 2, 3, 5, 7, 11, 13

Eigenschaften

Eine fermatsche Pseudoprimzahl q q\ ist mindestens zu einer Basis a a\ mit a≥2 a \ge 2\ pseudoprim.
Wenn eine ungerade fermatsche Pseudoprimzahl q q\ zu einer Basis a a\ mit a<q a < q\ pseudoprim ist, so ist q q\ auch zu der Basis (q−a) (q - a)\ pseudoprim.
Wenn eine fermatsche Pseudoprimzahl q q\ zu einer Basis a a\ mit a<q a < q\ pseudoprim ist, so ist q q\ auch zu der Basis an a^n\ mit einer natürlichen Zahl n≥1 n \ge 1\ pseudoprim.
Wenn eine fermatsche Pseudoprimzahl q q\ zu einer Basis der Form a a\ pseudoprim ist, so ist q q\ auch pseudoprim zu einer Basis a+nq a + nq\ mit einer natürlichen Zahl nn .
Demzufolge ist eine fermatsche Pseudoprimzahl q q\ zu jeder Basis b b\ pseudoprim, zu der eine der folgenden drei Bedingungen zutrifft:
b≡amod  qb \equiv a \mod q
b≡1mod  qb \equiv 1 \mod q
b≡(q−1)mod  qb \equiv (q-1) \mod q
Wobei a a\ eine Basis sein muß, zu der q q\ pseudoprim ist.

Beispiel

15 ist eine fermatsche Pseudoprimzahl, die zu folgenden Basen Pseudoprim ist: 4, 11, 19, 26, ...
414≡1mod  154^{14} \equiv 1 \mod 15 da 4=15−11  4 = 15-11\
1914≡1mod  1519^{14} \equiv 1 \mod 15 da 19≡4mod  15 19 \equiv 4 \mod 15
2614≡1mod  1526^{14} \equiv 1 \mod 15 da 26≡11mod  15 26 \equiv 11 \mod 15
...
Jede natürliche, zusammengesetzte Zahl n n\ ist eine fermatsche Pseudoprimzahl zu Basen der Form m⋅n+1m\cdot n+1 mit m≥1m \ge 1
(m⋅n+1)n−1≡1mod  n(m\cdot n+1)^{n-1} \equiv 1 \mod n

Einteilung

Die fermatschen Pseudoprimzahlen lassen sich in zwei Mengen aufteilen: Einmal in die, die zugleich auch eulersche Pseudoprimzahlen sind, und solche die keine eulerschen Primzahlen sind. Zu den ersteren gehören die fermatschen Pseudoprimzahlen zur Basis 2, die Carmichael-Zahlen und absoluten eulerschen Pseudoprimzahlen. Die zweite Menge hat keine Relevanz.
{ absolute eulersche Primzahlen } ⊂\subset { Carmichael-Zahlen } ⊂\subset { eulersche Pseudoprimzahlen } ⊂\subset { fermatsche Pseudoprimzahlen }
 
 

Manche Menschen haben einen Gesichtskreis vom Radius Null und nennen ihn ihren Standpunkt.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Fermatsche Pseudoprimzahl aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Mehr über Primzahlen