Edouard Lucas
Francois Eduoard Anatole Lucas (* 4. April 1842 in Amiens, † 3. November 1891 in Paris) war ein französischer Mathematiker.Lucas war Professor für Mathematik am Lycée Saint Louis in Paris und am Lycée Charlemagne, ebenfalls in Paris. Er hat sich stark mit Zahlentheorie beschäftigt und das Spiel Türme von Hanoi bekannt gemacht. Es erschien 1883 als Spielzeug unter Lucas Pseudonym "M. Claus". Dabei entstand "Claus" aus "Lucas" durch Buchstabenvertauschung.
Mit beliebigen reellen Startwerten a1 und a2 wird eine rekursiv definierten Zahlenfolge (Lucas-Folge) erklärt durch an+2 = an+1 + an. Dies ist eine Verallgemeinerung der Fibonacci-Zahlen. Wie bei der Fibonacci-Folge konvergiert der Quotient zweier aufeinanderfolgender Zahlen gegen den Goldenen Schnitt.
Lucas-Test
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.
Der Lucas-Test wurde 1930 von Derrick Henry Lehmer vereinfacht (siehe Lucas-Lehmer-Test).