Lucas-Lehmer prímteszt a Mersenne-számokhoz

A matematika , a Lucas-Lehmer teszt egy prímteszt a Mersenne számok . A vizsgálatot eredetileg a Édouard Lucas az 1878 és jelentősen javult Derrick Henry Lehmer az 1930-as években , az ő tanulmányi Lucas lakosztállyal .

Tétel

Mi határozza meg indukcióval a szekvencia egész számok ( s i ) i ≥0 szerint:

s0=4et∀én∈NEMsén+1=sén2-2.{\ displaystyle s_ {0} = 4 \ quad {\ rm {és}} \ quad \ forall i \ in \ mathbb {N} \ quad s_ {i + 1} = s_ {i} ^ {2} -2. }

Ennek a szekvenciának az első tagjai: 4, 14, 194  stb. ( az OEIS A003010 folytatása ).

Hadd p lesz egy prímszám más, mint 2. Az Mersenne száma M p  = 2 p - 1 prím akkor és csak akkor k p - 2 az osztható M p .

A szám s p - 2 mod M p az úgynevezett "Lucas-Lehmer maradékot" a p .

Példák

• Az M 3 = 7 Mersenne-szám elsődleges. A Lucas-Lehmer teszt ezt a következőképpen igazolja. Tól s 0 = 4, kiszámítjuk s 3 - 2 = s 1 = 4 2 - 2 = 14 ≡ 0 mod 7. Mivel a értéke s 1 mod 7 jelentése 0, a következtetés az, hogy M 3 prím.
• Másrészt az M 11  = 2047 = 23 × 89 nem elsődleges. Még egyszer, s 0 = 4, de most kiszámoljuk a modulo 2 047-et, az s szekvencia egymást követő tagjai a 11 - 2 = 9 indexig:
  • s 1 = 4 2 - 2 = 14
  • s 2 = 14 2 - 2 = 194
  • s 3 = 194 2 - 2 ≡ 788 mod 2 047
  • s 4 788 2 - 2 701 mod 2 047
  • s 5 ≡ 701 2 - 2 ≡ 119 mod 2 047
  • s 6 ≡ 119 2 - 2 ≡ 1 877 mod 2 047
  • s 7 ≡ 1 877 2 - 2 ≡ 240 mod 2 047
  • s 8 ≡ 240 2 - 2 ≡ 282 mod 2 047
  • s 9 ≡ 282 2 - 2 ≡ 1 736 mod 2 047

Mivel s 9 mod 2047 értéke nem 0, a következtetés az, hogy M 11 = 2047 nem prím.

Bizonyíték

Ezt a tesztet 1932-ben az AE Western mutatta be azzal, hogy a testbe helyezte ℚ (√3).

Ez a szakasz kiadatlan műveket vagy nem auditált kimutatásokat tartalmazhat  (2017. július) . Segíthet referenciák hozzáadásával vagy a közzé nem tett tartalom eltávolításával.

Szükségünk van, ha elsődleges, a másodfokú kölcsönösség egyszerű esete . 32o-1-1≡-1mod2o-1{\ displaystyle 3 ^ {2 ^ {p-1} -1} \ equiv -1 {\ bmod {2}} ^ {p} -1}2o-1{\ displaystyle 2 ^ {p} -1}

A ringben állunk . Z2o-1[3]={nál nél+b3mod2o-1}{\ displaystyle \ mathbb {Z} _ {2 ^ {p} -1} [{\ sqrt {3}}] = \ {a + b {\ sqrt {3}} {\ bmod {2}} ^ {p } -1 \}}

Mivel van . Egyébként . o∣2o-1-1{\ displaystyle p \ közepén 2 ^ {p-1} -1}22o-1-1≡1mod2o-1{\ displaystyle 2 ^ {2 ^ {p-1} -1} \ equiv 1 {\ bmod {2}} ^ {p} -1}2+3=12-3=(2.3+23)23.23{\ displaystyle 2 + {\ sqrt {3}} = {\ frac {1} {2 - {\ sqrt {3}}}} = {\ frac {(2.3 + 2 {\ sqrt {3}}) ^ { 2}} {3,2 ^ {3}}}}

• Ha ez az első , ezért2o-1{\ displaystyle 2 ^ {p} -1} (2.3+23)2o-1≡(binomiális képlet)(2.3)2o-1+(23)2o-1⏟322o-132o-1-1≡2.3-23mod2o-1{\ displaystyle (2.3 + 2 {\ sqrt {3}}) ^ {2 ^ {p} -1} \! \! \! \! \! \! {\ underset {\ scriptstyle {\ text {(binomiális képlet)} }} {\ equiv}} \! \! \! \! \! (2.3) ^ {2 ^ {p} -1} + \ underbrace {(2 {\ sqrt {3}}) ^ {2 ^ {p } -1}} _ {{\ sqrt {3}} 2 ^ {2 ^ {p} -1} 3 ^ {2 ^ {p-1} -1}} \ equiv 2.3-2 {\ sqrt {3} } {\ bmod {2}} ^ {p} -1}

(2+3)2o-1=(2.3+23)2o(3.23)2o-1≡(2.3+23)(2.3-23)-3.23≡-1mod2o-1(1){\ displaystyle (2 + {\ sqrt {3}}) ^ {2 ^ {p-1}} = {\ frac {(2,3 + 2 {\ sqrt {3}}) ^ {2 ^ {p}}} {(3,2 ^ {3}) ^ {2 ^ {p-1}}}} \ equiv {\ frac {(2,3 + 2 {\ sqrt {3}}) (2,3-2 {\ sqrt {3}}) } {- 3,2 ^ {3}}} \ equiv -1 {\ bmod {2}} ^ {p} -1 \ qquad \ qquad (1)}Vegyük észre, hogy (1) igaz, akkor és csak akkor , ha .So-2=(2-3)2o-2((2+3)2o-1+1)≡0mod2o-1{\ displaystyle S_ {p-2} = (2 - {\ sqrt {3}}) ^ {2 ^ {p-2}} \ balra ((2 + {\ sqrt {3}}) ^ {2 ^ { p-1}} + 1 \ jobbra) \ equiv 0 {\ bmod {2}} ^ {p} -1}S0=4,Snem+1=Snem2-2=(2+3)2nem+1+(2-3)2nem+1{\ displaystyle S_ {0} = 4, S_ {n + 1} = S_ {n} ^ {2} -2 = (2 + {\ sqrt {3}}) ^ {2 ^ {n + 1}} + (2 - {\ sqrt {3}}) ^ {2 ^ {n + 1}}}

• Most feltételezzük, hogy az (1) igaz, de ez nem elsődleges. Legyen ez a legkisebb elsődleges tényezője, így . Azt kapjuk2o-1{\ displaystyle 2 ^ {p} -1}q{\ displaystyle q}q2≤2o-1{\ displaystyle q ^ {2} \ leq 2 ^ {p} -1}

(1)⟹(2+3)2o-1≡-1modq{\ displaystyle (1) \ impluce (2 + {\ sqrt {3}}) ^ {2 ^ {p-1}} \ equiv -1 {\ bmod {q}}} 2o{\ displaystyle 2 ^ {p}}tehát a multiplikatív csoport sorrendje . De ennek a csoportnak vannak elemei, ahol . Tehát megtettük volna2+3{\ displaystyle 2 + {\ sqrt {3}}}Zq[3]×{\ displaystyle \ mathbb {Z} _ {q} [{\ sqrt {3}}] ^ {\ alkalommal}}r{\ displaystyle r}r≤q2-1{\ displaystyle r \ leq q ^ {2} -1} (2+3)r≡1modq{\ displaystyle (2 + {\ sqrt {3}}) ^ {r} \ equiv 1 {\ bmod {q}}}ellentmondás azóta .r≤q2-1<2o{\ displaystyle r \ leq q ^ {2} -1 <2 ^ {p}}

Végül elhelyezzük magunkat abban a gyűrűben, amely az egység harmadik gyökerét tartalmazza, amely igazolja , hogy ha elsődleges és ezért jó . Z2o-1[én,3]{\ displaystyle \ mathbb {Z} _ {2 ^ {p} -1} [i, {\ sqrt {3}}]}ζ3=-12+én32{\ displaystyle \ zeta _ {3} = - {\ frac {1} {2}} + i {\ frac {\ sqrt {3}} {2}}}ζ3-ζ32=én3{\ displaystyle \ zeta _ {3} - \ zeta _ {3} ^ {2} = i {\ sqrt {3}}}2o-1{\ displaystyle 2 ^ {p} -1}-én332o-1-1=(ζ3-ζ32)2o-1≡ζ32o-1-ζ32(2o-1)≡ζ3-ζ32≡én3mod2o-1{\ displaystyle -i {\ sqrt {3}} \, 3 ^ {2 ^ {p-1} -1} = (\ zeta _ {3} - \ zeta _ {3} ^ {2}) ^ {2 ^ {p} -1} \ equiv \ zeta _ {3} ^ {2 ^ {p} -1} - \ zeta _ {3} ^ {2 (2 ^ {p} -1)} \ equiv \ zeta _ {3} - \ zeta _ {3} ^ {2} \ equiv i {\ sqrt {3}} {\ bmod {2}} ^ {p} -1}32o-1-1≡-1mod2o-1{\ displaystyle 3 ^ {2 ^ {p-1} -1} \ equiv -1 {\ bmod {2}} ^ {p} -1}

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben az angol Wikipedia "  Lucas - Lehmer primality teszt  " című cikkéből származik ( lásd a szerzők felsorolását ) .

1. (in) DH Lehmer, "  Lucas funkcióinak kiterjesztett elmélete  " , Ann. Math. , 2 ND sorozat, vol.  31,1930, P.  419-448 ( JSTOR  1968235 ).
2. (in) DH Lehmer, "  Lucas tesztje a Mersenne-számok elsődlegességére  " , J. London Math. Soc. , vol.  10,1935, P.  162–165 ( online olvasás ).
3. Ez a folytatás is szokatlan az eredeti Lehmer cikkek, és (en) Chris Caldwell, "  A bizonyíték a Lucas-Lehmer Test  " , a Prime Pages és (en) Benjamin Finom és Gerhard Rosenberger, számelmélet: Bevezetés keresztül Distribution of Primes , Springer,2007( online olvasható ) , p.  226 : S i = S i + 1 és S 1 = 4 és S k = S k -1 2 - 2. Az a feltétel, ezután beírjuk: S p - 1 osztható m o .
4. (in) Paulo Ribenboim , The Little Book of Bigger Primes , Springer ,2004, 2 nd  ed. , 356  p. ( ISBN  978-0-387-20169-6 , online olvasás ) , p.  77-78.
5. (in) Eric W. Weisstein , "  Lucas-Lehmer teszt  " a mathworld .
6. (in) AE Western, "  Lucas és Pepin tesztje a Mersenne-féle számok primenesséért  " , Journal of the Mathematical Society of London ,1932.
7. (in) JW Bruce, "  A Lucas-Lehmer teszt valóban triviális bizonyítéka  " , American Mathematical Monthly , vol.  100, n o  4,1993, P.  370–371 ( DOI  10.2307 / 2324959 )

Kapcsolódó cikkek

• Remek internetes Mersenne Prime Search
• Prime95
• Lucas-Lehmer teszt-Riesel  (en)