Lucas kriterium

Lucas kriterium är en sats från talteorin och är uppkallat efter den franske matematikern Édouard Lucas (1842-1891). Kriteriet lyder: Om p är ett primtal större än 2, så är Mersennetalet M_p = 2^p - 1 ett primtal om och endast om M_p är en delare till det p-1:te Lucastalet L_p-1.

Lucas talföljd bildas rekursivt enligt följande: L₁ = 4 och L _i+1 = L_i² - 2, varvid man får följden: 4, 14, 194, 37634, 1416317954,...

Med hjälp av kriteriet testade Lucas om M₁₂₇ = 2¹²⁷ - 1 var ett primtal och fann att så var fallet. Testet, som utfördes för hand, var klart 1876. Talet var det största kända primtalet fram till 1940-talet.

Exempel. M₅ = 2⁵ - 1 = 31. Detta tal delar L₄ = 37634 och är därmed, enligt kriteriet, ett primtal.

Källor

• Édouard Lucas and primality testing, Hugh Williams, Wiley & Sons, New York 1998.