Test Lucas-Lehmer

Testul Lucas-Lehmer este o verificare a primalității primilor Mersenne . Pe scurt, pentru $p$ ${\ displaystyle p}$ $p$ numărul prim, a spus $M_{p}=2^{p}-1$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$ the $p$ ${\ displaystyle p}$ $p$ -al număr Mersenne, este prim dacă și numai dacă se împarte $L_{p-1}$ ${\ displaystyle L_ {p-1}}$ ${\ displaystyle L_ {p-1}}$ , unde este $L_{n}$ ${\ displaystyle L_ {n}}$ ${\ displaystyle L_ {n}}$ este al n-lea termen al secvenței definit recursiv ca:

L_{n+1}=L_{n}^{2}-2

{\ displaystyle L_ {n + 1} = L_ {n} ^ {2} -2}

{\ displaystyle L_ {n + 1} = L_ {n} ^ {2} -2}

începând de la

L_{1}=4

{\ displaystyle L_ {1} = 4}

{\ displaystyle L_ {1} = 4}

Testul a fost inițial dezvoltat de matematicianul Édouard Lucas în 1870 și simplificat de Derrick Norman Lehmer în 1930 . Testul este atât de rapid și ușor de programat, încât în 1978 doi elevi de liceu au dovedit numărul Mersenne $2^{21701}-1$ ${\ displaystyle 2 ^ {21701} -1}$ ${\ displaystyle 2 ^ {21701} -1}$ este prim, depășind recordul anterior al celui mai mare număr prim cunoscut de atunci.

De asemenea, este posibilă o optimizare a timpului de calcul, pentru a face față unor numere mai mari, având în vedere acest lucru $L_{n}$ ${\ displaystyle L_ {n}}$ $L_ {n}$ crește foarte repede, odată cu creșterea $n$ ${\ displaystyle n}$ $n$ , pentru a deveni rapid intratabil. Puteți înlocui succesiunea anterioară cu cea specifică pentru numărul de verificat $M_{n}$ ${\ displaystyle M_ {n}}$ $M_n$ , obținut după cum urmează:

L_{n+1}\equiv (L_{n}^{2}-2)\,\operatorname {mod} \,M_{p}

{\ displaystyle L_ {n + 1} \ equiv (L_ {n} ^ {2} -2) \, \ operatorname {mod} \, M_ {p}}

{\ displaystyle L_ {n + 1} \ equiv (L_ {n} ^ {2} -2) \, \ operatorname {mod} \, M_ {p}}

unde mod este modulul , adică restul diviziunii prin $M_{p}$ ${\ displaystyle M_ {p}}$ $M_p$ . Cu toate acestea, această secvență are dezavantajul de a fi utilă numai pentru numerele Mersenne mai mici sau egale cu $M_{p}$ ${\ displaystyle M_ {p}}$ $M_p$ .

Afirmație

Fie p un număr prim. Numărul corespunzător de Mersenne $M_{p}=2^{p}-1$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$ este prim dacă și numai dacă:

L_{p-1}\equiv 0\,\operatorname {mod} \,M_{p}

{\ displaystyle L_ {p-1} \ equiv 0 \, \ operatorname {mod} \, M_ {p}}

{\ displaystyle L_ {p-1} \ equiv 0 \, \ operatorname {mod} \, M_ {p}}

Observare

Nu este restrictiv să luăm în considerare numerele Mersenne $M_{p}$ ${\ displaystyle M_ {p}}$ $M_p$ cu $p$ ${\ displaystyle p}$ $p$ mai întâi în loc de $M_{n}$ ${\ displaystyle M_ {n}}$ $M_n$ cu $n$ ${\ displaystyle n}$ $n$ numar natural. De fapt, se arată că dacă $n$ ${\ displaystyle n}$ $n$ este compus, apoi și $M_{n}$ ${\ displaystyle M_ {n}}$ $M_n$ este.

Demonstrație

Pentru suficiență: sunt $u=2+{\sqrt {3}}$ ${\ displaystyle u = 2 + {\ sqrt {3}}}$ ${\ displaystyle u = 2 + {\ sqrt {3}}}$ Și $v=2-{\sqrt {3}}$ ${\ displaystyle v = 2 - {\ sqrt {3}}}$ ${\ displaystyle v = 2 - {\ sqrt {3}}}$ . Apoi este ușor să arăți prin inducție că

L_{n}=u^{2^{n-1}}+v^{2^{n-1}}

{\ displaystyle L_ {n} = u ^ {2 ^ {n-1}} + v ^ {2 ^ {n-1}}}

{\ displaystyle L_ {n} = u ^ {2 ^ {n-1}} + v ^ {2 ^ {n-1}}}

Atâta timp cât $M_{p}$ ${\ displaystyle M_ {p}}$ $M_p$ împarte $L_{p-1}$ ${\ displaystyle L_ {p-1}}$ ${\ displaystyle L_ {p-1}}$ , există un număr întreg $R.$ ${\ displaystyle R}$ $R.$ astfel încât

L_{p-1}=R\,M_{p}

{\ displaystyle L_ {p-1} = R \, M_ {p}}

{\ displaystyle L_ {p-1} = R \, M_ {p}}

sau

u^{2^{p-2}}+v^{2^{p-2}}=R\,M_{p}

{\ displaystyle u ^ {2 ^ {p-2}} + v ^ {2 ^ {p-2}} = R \, M_ {p}}

{\ displaystyle u ^ {2 ^ {p-2}} + v ^ {2 ^ {p-2}} = R \, M_ {p}}

Înmulțind cu $u^{2^{p-2}}$ ${\ displaystyle u ^ {2 ^ {p-2}}}$ ${\ displaystyle u ^ {2 ^ {p-2}}}$ , Eu iau

1)\,\,\,\,\,u^{2^{p-1}}=R\,M_{p}u^{2^{p-2}}-1

{\ displaystyle 1) \, \, \, \, \, u ^ {2 ^ {p-1}} = R \, M_ {p} u ^ {2 ^ {p-2}} - 1}

{\ displaystyle 1) \, \, \, \, \, u ^ {2 ^ {p-1}} = R \, M_ {p} u ^ {2 ^ {p-2}} - 1}

Pătrat

2)\,\,\,\,\,u^{2^{p}}=\left(R\,M_{p}u^{2^{p-2}}-1\right)^{2}

{\ displaystyle 2) \, \, \, \, \, u ^ {2 ^ {p}} = \ left (R \, M_ {p} u ^ {2 ^ {p-2}} - 1 \ right ) ^ {2}}

{\ displaystyle 2) \, \, \, \, \, u ^ {2 ^ {p}} = \ left (R \, M_ {p} u ^ {2 ^ {p-2}} - 1 \ right ) ^ {2}}

Procedăm absurd. să presupunem că $M_{p}$ ${\ displaystyle M_ {p}}$ $M_p$ este compus și își ia divizorul d mai puțin decât rădăcina pătrată . Fie G grupul de numere din formă $\left(a+b{\sqrt {3}}\right)\,\operatorname {mod} \,d$ ${\ displaystyle \ left (a + b {\ sqrt {3}} \ right) \, \ operatorname {mod} \, d}$ ${\ displaystyle \ left (a + b {\ sqrt {3}} \ right) \, \ operatorname {mod} \, d}$ care sunt și ele inversabile: G are cel mult $d^{2}-1$ ${\ displaystyle d ^ {2} -1}$ ${\ displaystyle d ^ {2} -1}$ elemente. Dacă rescriem forma 1 și 2 d , obținem $u^{2^{p-1}}\equiv -1\,\operatorname {mod} \,d$ ${\ displaystyle u ^ {2 ^ {p-1}} \ equiv -1 \, \ operatorname {mod} \, d}$ ${\ displaystyle u ^ {2 ^ {p-1}} \ equiv -1 \, \ operatorname {mod} \, d}$ Și $u^{2^{p}}\equiv 1\,\operatorname {mod} \,d$ ${\ displaystyle u ^ {2 ^ {p}} \ equiv 1 \, \ operatorname {mod} \, d}$ ${\ displaystyle u ^ {2 ^ {p}} \ equiv 1 \, \ operatorname {mod} \, d}$ respectiv. Deci u este un element al lui G al perioadei $2^{p}$ ${\ displaystyle 2 ^ {p}}$ ${\ displaystyle 2 ^ {p}}$ . Deoarece perioada unui element poate fi cel mult egală cu numărul de elemente din grup, avem următoarea inegalitate