Number theory Finite fields and computational number theory Theorem

Lucas–Lehmer test

Builds on Mersenne number Congruence modulo n

Statement

Let $p$ be an odd prime, and let $M_p = 2^p - 1$ be the Mersenne number. Define the sequence $(s_i)_{i \ge 0}$ by $s_0 = 4$ and $s_i = s_{i-1}^2 - 2$ for $i \ge 1$ . Then $M_p$ is prime if and only if $s_{p-2} \equiv 0 \pmod{M_p}$ .

Remarks

For example, take $p = 5$ and $M_5 = 31$ . Modulo $31$ , the sequence is $4, 14, 8, 0$ , so $s_3 \equiv 0$ and $31$ is prime. In practice, one reduces each term modulo $M_p$ . Then the test needs $p - 2$ squarings of numbers with at most $p$ bits.

History

Édouard Lucas developed the test in 1878, and Derrick Henry Lehmer proved it in 1930.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Mersenne number definition
Congruence modulo n definition
Lucas–Lehmer test statement

Tag	`061BTYA0RN`
URI	`m2://061BTYA0RN`
Aliases	`lucas-lehmer-primality-test`
Kind	statement, theorem
Writing	W1 stated
MSC	11Y11
Status	This copy of the site has no build data. Run `m2 status 061BTYA0RN`.
Uses	Mersenne number, Congruence modulo n
Same as	Wikidata Q1138992 Wikipedia Lucas–Lehmer primality test

Lucas–Lehmer test

Statement

Remarks

History

Reading path

Further reading

What this page needs for W2

What links here