Benutzer:Tanik/Lucas-Lehmer-Test für Mersennezahlen

Lucas-Lehmer-Test für Mersennezahlen

Im Lucas-Lehmer-Test für Mersennezahlen besteht die Schwierigkeit darin, die Primfaktoren von $n+1$ und entsprechende Lucas-Folgen zu finden. Die Mersennezahlen $M_{m}=2^{m}-1,m\ngeqslant 1\,$ haben die Eigenschaft, dass $n+1$ in diesem Fall eine Potenz von 2 ist und hat nur einen Primfaktor. Deshalb können wir Lucas-Lehmer-Test für Mersennezahlen so formulieren:

Bemerkung (Lucas-Lehmer-Test für Mersennezahlen)  

Wenn eine Lucas-Folge ${}U_{n}\,$ mit

${}U_{n+1}\equiv 0\,\,\,(mod\,n)\,$

bei

${}U_{\frac {n+1}{2}}\equiv 0\,\,\,(mod\,n)\,$

existiert, dann ist ${}n=M_{m}=2^{m}-1\,$ prim.

Lemma

${}U_{k}\,$ und ${}V_{k}\,$ haben höchstens ${}2Q^{k}\,$ als gemeisamen Teiler, sprich ${}ggT(U_{k},V_{k})$.

Beweis

Benutzer:Tanik/Lucas-Lehmer-Test für Mersennezahlen/Lemma2/Beweis

$\Box$

Die Bedingungen $U_{n+1}\equiv 0\,\,\,(mod\,n)$ und $U_{\frac {n+1}{2}}\equiv 0\,\,\,(mod\,n)$ können zusammengefasst werden.

Es gilt $U_{n+1}={\frac {U_{n+1}}{2}}{\frac {V_{n+1}}{2}}\,,$ womit ${\frac {V_{n+1}}{2}}\equiv 0\,\,\,(mod\,\,n)\,$ sein muss. Durch allgemeine Bedingung $\,ggT(2QcD,p)=1\,,$ an Lucas-Folgen für Primzahltests und Lemma auch klar, dass wenn ${\frac {V_{n+1}}{2}}\,$ den Faktor $n\,$ enthält, ${\frac {V_{n+1}}{2}}\not \equiv 0\,\,\,(mod\,\,n)\,$ sein muss. Es gegügt demnach ${\frac {V_{n+1}}{2}}=V_{2^{m-1}}\equiv 0\,\,\,(mod\,\,n)\,$ zu überprüfen.

Es sei $V_{2^{k}}:=v_{k}\,.$

Die Berechnung $V_{2^{k}}=V_{2^{k-1}}^{2}-2Q^{2^{k-1}}\,$ dadurch die Form $v_{k}=v_{k-1}^{2}-2Q^{2^{k-1}}\,.$ Begonnen wird die Rekursion mit $v_{0}=V_{1}=P\,$ und die Frage bezüglich der Primalität von $M_{m}\,$ lässt sich wie folgt formulieren: wann ist $v_{m-1}\equiv 0\,\,\,(mod\,\,M_{m})\,?$

Die Werte $a=1+{\sqrt {3}},b=1-{\sqrt {3}}\,$ ergeben eine passende Lucas-Folge, das führt zu

$P=2,Q=-2,P^{2}-4Q=12,D=3,C=2\,.$

Dadurch sieht die Rekursion wie folgt aus: $v_{k}=v_{k-1}^{2}-22^{2^{k-1}}\,$ mit dem Startwert $v_{1}=v_{0}^{2}+4=8\,.$

Bemerkung (Lucas-Lehmer-Test für Mersennezahlen alternativ)  

Es sei m ungerade, dann ist ${}M_{m}=2^{m}-1\,$ genau dann prim, wenn ${}v_{m-1}\equiv 0\,\,\,(mod\,\,M_{m})\,$, wobei ${}v_{1}=8\,$ und ${}v_{k}=v_{k-1}^{2}-22^{2^{k-1}}\,$.

Verbesserter Lucas-Lehmer-Test für Mersennezahlen

Satz (Verbesserter Lucas-Lehmer-Test für Mersennezahlen)

Sei ${}n=2^{p}-1\,$ für eine ungerade Primzahl. Die Folge ${}v_{k}\,$ sei rekursiv definiert durch ${}v_{1}=4\,$ und ${}v_{k}=v_{k-1}^{2}-2\,$. Dann ist ${}n\,$ genau dann prim, falls ${}n\,$ die Zahl ${}v_{p-1}\,$ teilt.

Beweis

Benutzer:Tanik/Lucas-Lehmer-Test für Mersennezahlen//Beweis

$\Box$

Beispiel

Man zeige, dass ${}n=2^{5}-1=31\,$ prim ist.

Wir berechnen alle ${}v_{k},k=1,2,3,4\,$ aus:

${}v_{1}=4\,$,

${}v_{2}=4^{2}-2=14\,$,

${}v_{3}=14^{2}-2=194\equiv 8\,\,\,(mod\,\,31)\,$,

${}v_{4}=8^{2}-2=62\equiv 0\,\,\,(mod\,\,31)\,$.

Daraus nach verbessertem Lucas-Lehmer-Test für Mersennezahlen folgt, dass die Zahl ${}31$ prim ist.

Beispiel

Man zeige, dass ${}n=2^{1}1-1=2047\,$ nicht prim ist.

Wir berechnen alle ${}v_{k},k=1,\ldots ,10\,$ aus:

${}v_{1}=4\,,v_{2}=4^{2}-2=14\,$,

${}v_{3}=14^{2}-2=194\equiv 8\,,v_{4}=194^{2}-2\equiv 788\,\,\,(mod\,\,2047)\,$,

${}v_{5}=788^{2}-2\equiv 701\,\,\,(mod\,\,2047)\,,v_{6}=701^{2}-2\equiv 119\,\,\,(mod\,\,2047)\,$,

${}v_{7}=119^{2}-2\equiv 1877\,\,\,(mod\,\,2047)\,,v_{8}=1877^{2}-2\equiv 240\,\,\,(mod\,\,2047)\,$,

${}v_{9}=240^{2}-2\equiv 282\,\,\,(mod\,\,2047)\,,v_{1}0=282^{2}-2\equiv 1736\,\,\,(mod\,\,2047)\,$.

D.h. ${}n\nshortmid v_{10}\,$ und nach verbessertem Lucas-Lehmer-Test für Mersennezahlen folgt, dass die Zahl${}2047$ nicht prim ist. Und tatsächlich ${}2047=23\cdot 89$.

Literatur

• Müller-Stach,S./Piontkowski, J.: Elementare und algebraische Zahlentheorie. 1. Auflage Wiesbaden : Vieweg, 2006, ISBN 978-3-8348-0211-8
• Paulo Ribenboim, Die Welt der Primzahlen: Geheimnisse und Rekorde, Springer-Verlag Berlin Heidelberg, 2006 ISBN 978-3-540-34284-7
• Riesel,H.: Prime Numbers and Computer Methods for Factorization, Birkhäuser, ISBN 0-8176-3291-3
• Burton, D.M./Dalkowski, H.: Handbuch der elementaren Zahlentheorie. Neldermann Verlag, 2005, ISBN 3-88538-112-5