Quelltext der Seite Der Lucas-Test für Mersennsche Primzahlen

{{inputbild|Seitenhalbierende mit schwerpunkt|svg| 200px {{!}}  {{!}} Bildkommentar }}

{{
mathdisplay|term=
M=\{ a \in \mathbb N \mid a \text{ gerade} \}
|SZ=
}}

{{math|term=\text{ für }  \text{ also } |SZ= }}


{{Zwischenüberschrift|<u>Lucas-Test</u>}}


{{inputfaktbeweis|qetklweth/Fakt|  | }}

{{inputdefinition| 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 <math>a^{p-1}\equiv 1\mod p </math> 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 <math>a^{N-1}\equiv 1\mod N </math> .
Lucas entdeckte im Jahre 1876 eine richtige Umkehrung von Fermats kleinem Satz. Diese besagt:


[[Datei:Elucas 1.png|mini|Lucacscsc]]


{{inputfakt|Benutzer:Abrankov/1/Fakt|Test 1|( )}}


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


Lucas gab 1891 den folgenden Test an:



{{inputfaktbeweis|/Verbesserter Test/Fakt|Test 2|( )}}



{{inputfaktbeweis|/Brillhart/Fakt|Test 3|( )}}



{{inputfaktbeweis|Benutzer:Abrankov/Pocklington Test/Fakt|Satz|Pocklington|ref1=( )}}



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

{{Zwischenüberschrift|Fermatsche Primzahlen}}



[[Datei:Pierre de Fermat.png|mini]]
{{inputdefinition|Primzahlen/Fermatsche PrimzahlenDefinition|Fermatsche Primzahlen}}


{{inputdefinition|Fermatsche Primzahlen/Exponentenlemma/Fakt|}}


{{inputdefinition|Fermat Zahlen/Definition|Fermat-Zahlen}}


{{inputfaktbeweis|Benutzer:Abrankov/Pepin Test|Satz|Pepin Test}}





{{inputbeispiel|Benutzer:Abrankov/Pepin Test|Beispiel|()}}