Fermatsche Pseudoprimzahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

a^{n-1} \equiv 1 \mod n

für die zu n teilerfremde Zahl a erfüllt ist.

Anders ausgedrückt muss n die Differenz a^{n-1}-1 teilen.

Zum Beispiel ist 341 eine Fermatsche Pseudoprimzahl zur Basis 2, da 341 ein Teiler von 2^{340}-1, aber aufgrund 341=11·31 nicht prim ist.

Eine Fermatsche Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf das Kriterium des kleinen Fermatschen Satzes. Dieses Kriterium wird beim Fermatschen Primzahltest verwendet.

Definition[Bearbeiten]

Eine Fermatsche Pseudoprimzahl zur Basis a ist eine zusammengesetzte, natürliche Zahl n, für die

a^{n-1} \equiv 1 \mod n

gilt. In Bezug auf die Basis a verhält sich n also wie eine Primzahl.

Beispiel: Die Zahl 91 ist eine Fermatsche Pseudoprimzahl bezüglich der Basen 17, 29 und 61, da 17^{90}-1, 29^{90}-1 und 61^{90}-1 durch 91 teilbar sind. Obwohl die Zahl 91 keine Primzahl ist (91 = 7·13), erfüllt sie also für einige a den kleinen Fermatschen Satz.

Unterklassen und Eigenschaften[Bearbeiten]

Zu den Fermatschen Pseudoprimzahlen gehören die Carmichael-Zahlen, die Eulersche Pseudoprimzahlen und die absoluten Eulerschen Pseudoprimzahlen.

Ist n eine Fermatsche Pseudoprimzahl zur Basis a, so auch zur Basis ak und zu a + kn (k > 1), sowie - falls n ungerade ist und a < n - zur Basis n - a.

Die Folgen der Fermatschen Pseudoprimzahlen zu den Basen 2, 3 und 5[Bearbeiten]

Zu jeder Basis gibt es unendlich viele Fermatsche Pseudoprimzahlen. Diese lauten beispielsweise

Basis 2

341, 561, 645, 1105, 1387, 1729, 1905, … (Folge A001567 in OEIS).

Basis 3

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, … (Folge A005935 in OEIS).

Basis 5

4, 124, 217, 561, 781, 1541, 1729, 1891, … (Folge A005936 in OEIS).

Konstruktion unendlich vieler Fermatscher Pseudoprimzahlen zu jeder Basis[Bearbeiten]

Michele Cipolla konstruierte im Jahr 1904 auf folgende Weise unendlich viele Fermatsche Pseudoprimzahlen zu jeder Basis:

Für jedes a > 1 und jede ungerade Primzahl p, die a(a^2-1) nicht teilt, ist

n=\frac{a^p-1}{a-1}\cdot\frac{a^p+1}{a+1}

eine Fermatsche Pseudoprimzahl zur Basis a.[1] Da es unendlich viele Primzahlen gibt, muss es demnach auch zu jeder Basis unendlich viele Fermatsche Pseudoprimzahlen geben. Beispiele:

a p 1. Faktor 2. Faktor n Primfaktorzerlegung
2 5 31 11 341 11·31
2 7 127 43 5461 43·127
3 5 121 61 7381 11·11·61
3 7 1093 547 597871 547·1093
7 5 2801 2101 5884901 11·191·2801

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Zum Beweis siehe G. H. Hardy, E. M. Wright: An introduction to the theory of numbers, Oxford University Press, 2005, Seite 90.

Weblinks[Bearbeiten]