Diskussion:Lucas-Test (Mathematik)

Letzter Kommentar: vor 19 Jahren von Ruhri in Abschnitt Test falsch herum

Lucas-Test (aus Edouard Lucas)

Bearbeiten

Nach dem kleinen Satz von Fermat gilt für eine zur Primzahl p teilerfremde Zahl a die Kongruenz ap-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 27-1 mod 7 = 1; 37-1 mod 7 = 1; 47-1 mod 7 = 1; 57-1 mod 7 = 1 und 67-1 mod 7 = 1). Man kann jedoch nicht aus der Tatsache, dass eine Zahl p die Bedingung erfüllt, schlussfolgern, dass p Primzahl ist: 415-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:

 

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

 

die Zahl Mn als Teiler hat. Beispiel: Für M5 = 31 erhält man
x1 = 4
x2 = 4² - 2 = 14
x3 = 14² - 2 = 194
x4 = 194² - 2 = 37634
37634 ist durch 31 teilbar (37634 = 1214 · 31), also ist 31 eine Primzahl.

Ein Widerspruch

Bearbeiten

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.   und
  2.   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:

  - Stimmt.

Aber die zweite Bedingung:

  - 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

Bearbeiten

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)Beantworten

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

Bearbeiten

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!