Diskussion:Lucas-Test (Mathematik)

Lucas-Test (aus Edouard Lucas)

Nach dem kleinen Satz von Fermat gilt für eine zur Primzahl p teilerfremde Zahl a die Kongruenz a^p-1 ≡ 1 mod p. Das heißt, wenn eine Zahl p Primzahl ist, dann genügt sie der genannten Bedingung (Zum Beispiel ist 7 eine Primzahl, also gilt 2^7-1 mod 7 = 1; 3^7-1 mod 7 = 1; 4^7-1 mod 7 = 1; 5^7-1 mod 7 = 1 und 6^7-1 mod 7 = 1). Man kann jedoch nicht aus der Tatsache, dass eine Zahl p die Bedingung erfüllt, schlussfolgern, dass p Primzahl ist: 4^15-1 mod p = 1, aber 15 ist keine Primzahl. Daher nennt man Zahlen, die den Fermat-Test erfüllen, Pseudo-Primzahlen.

Lucas hat 1876 den Fermat-Test weiterentwickelt. Der Lucas-Test lautet: Eine Zahl ist genau dann eine Primzahl, wenn n den Fermat-Test zur Basis a besteht und für jeden Primteiler p von n-1 gilt:

$a^{\frac {n-1}{p}}\equiv 1\;mod\;n$

Speziell für Mersenne-Zahlen M_n kann dies wesentlich vereinfacht werden, da M_n - 1 nach Voraussetzung nur den Primteiler 2 hat. Damit liefert der Lucas-Test folgendes Kriterium: Die Mersenne-Zahl M_n ist genau dann eine Primzahl, wenn der Term x_n-1 der Lucas-Folge

$x_{1}=4;\,x_{n+1}=x_{n}^{2}-2$

die Zahl M_n als Teiler hat. Beispiel: Für M₅ = 31 erhält man
x₁ = 4
x₂ = 4² - 2 = 14
x₃ = 14² - 2 = 194
x₄ = 194² - 2 = 37634
37634 ist durch 31 teilbar (37634 = 1214 · 31), also ist 31 eine Primzahl.

Ein Widerspruch

Jetzt hatte ich gehofft, daß alles klar wäre, aber Pustekuchen. Ich habe Probleme mit dem Fermatschen Primzahltest, den ich eigentlich ergänzen wollte.

Der Fermatsche Satz funktioniert als Primzahltest unter folgender Bedingung:

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

für N > 1 und a > 1, wobei N die zu prüfende Zahl ist.

Mit dem kleinen Fermatschen Satz, der ersten Bedingung gibt es keine Probleme:

$2^{7-1}\equiv 1\mod 7$ - Stimmt.

Aber die zweite Bedingung:

$2^{3}\equiv 1\mod 7$ - Das dürfte nicht sein, da die 7 nachweislich eine Primzahl ist. Wo liegt der Fehler, beziehungsweise, wie müßte die zweite Bedingung korrekt heissen? --Arbol01 19:18, 19. Okt 2004 (CEST)</math>

Test falsch herum

Ich würde doch eher vermuten, dass man mit dem a durch alle Zahlen laufen muss und der kleine Fermat immer gelten muss. Sh. auch Fermatscher Primzahltest

Ruhri 19:37, 23. Mai 2005 (CEST)

Wieder umgedreht. Doch, es stimmt, zuerst wird der kleine Fermat getestet, denn wenn dieser nicht zutrifft, kann man sich den restlichen Durchlauf ersparen. --Arbol01 11:10, 30. Mär 2006 (CEST)

Mehrdeutigkeit des Begriffes

Ich habe am Beginn des Artikels auf die Bedeutung des Begriffes Lucas-Test im Sinne der organischen Chemie hingewiesen. Könnte jemand eine Begriffsdefintion mit mehreren Links für diesen Begriff einfügen, sodass man dann auf zwei Artikel (Lucas-Test(Mathematik), Lucas-Test(Chemie) zugreifen kann. Ich kann das leider nicht, darum bitte ich hier darum!

Doch, das kannst Du auch. Ich fange mal an! --Arbol01 16:32, 19. Jun 2005 (CEST)

Ich gehe davon aus, das Lucas-Probe das bessere Lemma ist. Dann würde sich eine Aufteilung eigentlich erübrigen. Wenn gewünscht, könnte man also Lucas-Test (Mathematik) wieder nach Lucas-Test zurückführen. --Arbol01 17:08, 19. Jun 2005 (CEST)

@Arbol: da hast du recht!