Lucas-Lehmer Test
A Mersenne Number 
is prime Iff divides 
, where 
and
 | (1) |
. The first few terms of this series are 4, 14, 194, 37634, 1416317954,... (Sloane's A003010). The remainder when is divided by is called the Lucas-Lehmer Residue for
. The Lucas-Lehmer Residue is 0 Iff is Prime. This test can also be extended to arbitraryIntegers.A generalized version of the Lucas-Lehmer test lets
 | (2) |
the distinct Prime factors, and 
their respective Powers. If there exists a Lucas Sequence
such that | (3) |
, ..., 
and | (4) |
is a Prime. The test is particularly simple for Mersenne Numbers, yielding the conventionalLucas-Lehmer test.See also Lucas Sequence, Mersenne Number, Rabin-Miller Strong Pseudoprime Test
References
Sloane, N. J. A. SequenceA003010/M3494in ``An On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.
- Hadwiger's Principal Theorem
- Hafner-Sarnak-McCurley Constant
- Hahn-Banach Theorem
- Hailstone Number
- Hairy Ball Theorem
- Half
- Half-Closed Interval
- Half-Normal Distribution
- Half-Open Interval
- Halley's Irrational Formula
- Halley's Method
- Halley's Rational Formula
- Hall-Janko Group
- Halphen Constant
- Halphen's Transformation
- Halting Problem
- Hamiltonian Circuit
- Hamiltonian Cycle
- Hamiltonian Graph
- Hamiltonian Group
- Hamiltonian Map
- Hamiltonian Path
- Hamiltonian System
- Hamilton's Equations
- Hamilton's Rules