Der Lucas-Test für Mersennsche Primzahlen

${}M=\{a\in \mathbb {N} \mid a{\text{ gerade}}\}\,$

${}{\text{ für }}{\text{ also }}$

Lucas-Test

Qetklweth/Fakt

Beweis

Qetklweth/Fakt/Beweis

$\Box$

Definition

Hier Definitionsname einsetzen /Definition

Der Satz von Wilson, der ja eine Charakterisierung der Primzahlen darstellt, scheint zunächst als Primzahltest vielversprechend zu sein.Da die Berechnung der Fakultät jedoch viel zu aufwändig ist, scheideter als praktischer Test aus.

Der kleine Satz von Fermat lautet für primes p und eine natürliche Zahl a, die kein Vielfaches von p ist, dass $a^{p-1}\equiv 1\mod p$ erfüllt ist. Allerdings möchten wir an dieser Stelle anmerken, dass die Umkehrung dieses Satzes nicht gilt – es gibt zerlegbare Zahlen N und a ≥ 2 mit $a^{N-1}\equiv 1\mod N$ . Lucas entdeckte im Jahre 1876 eine richtige Umkehrung von Fermats kleinem Satz. Diese besagt:

Lucacscsc

Test 1 (( ))

Es sei N >1. Angenommen, es existiert eine ganze Zahl a > 1

mit den Eigenschaften

1. $a^{N-1}\equiv 1\mod N\equiv 1\mod N$,
2. $a^{m}\equiv 1\mod N$ für $m=1,2,...,N-2$.

Dann ist N prim.

Das Problem dieses zunächst perfekt aussehenden Tests: Er benötigt $N-2$aufeinander folgende Multiplikationen mit a und das Finden der Reste modulo N – dies sind zuviele Operationen.

Lucas gab 1891 den folgenden Test an:

Test 2 (( ))

/Verbesserter Test/Fakt

Beweis

/Verbesserter Test/Fakt/Beweis

$\Box$

Test 3 (( ))

/Brillhart/Fakt

Beweis

/Brillhart/Fakt/Beweis

$\Box$

Satz (Pocklington)

Sei ${}n$ eine natürliche Zahl, so dass ${}n-1$ eine Faktorisierung der Form ${}n-1=RF$ besitzt, wobei alle Primteiler von ${}F$ bekannt sind. Weiterhin gebe es eine natürliche Zahl ${}0<a<n$ mit

1. ${}a^{n-1}\equiv 1\mod n$
2. ${}{ggT}\,(a^{\frac {n-1}{q}}-1,n)=1$

für alle Primteiler ${}q$ von ${}F$. Ist dann ${}F\geq {\sqrt {n}}$, so ist ${}n$ eine Primzahl.

Beweis

Benutzer:Abrankov/Pocklington Test/Fakt/Beweis

$\Box$

Für die Fermatschen Primzahlen reicht es aus, im Lucas Test die Zahl a = 3 zu überpriifen:

Fermatsche Primzahlen

Definition (Fermatsche Primzahlen)

Primzahlen/Fermatsche PrimzahlenDefinition

Definition

Bei einer Fermatschen Primzahl ${}2^{s}+1$ hat der Exponent die Form ${}s=2^{r}$ mit einem ${}r\in \mathbb {N}$.

Definition (Fermat-Zahlen)

Eine Zahl der Form ${}2^{2^{r}}+1$, wobei ${}r$ eine natürliche Zahl ist, heißt Fermat-Zahl.

Satz (Pepin Test)

Die Zahl

${}F_{r}=2^{2^{r}}+1{,}\,\,\ r\geq 1$, ist genau dann eine Primzahl, falls

${}3^{\frac {F_{r}-1}{2}}\equiv -1\mod F_{k}\,.$

Beweis

Benutzer:Abrankov/Pepin Test/Beweis

$\Box$

Beispiel (Beispiel)

Die Zahl ${}F_{r}=2^{2^{r}}+1{,}\,\,\ r\geq 1$, ist genau dann eine Primzahl, falls

${}3^{\frac {F_{r}-1}{2}}\equiv -1\mod F_{k}\,.$