Lucas-Lehmer Test

Theorem

Let $q$ be an odd prime.

Let $\left \langle {L_n} \right \rangle$ be a sequence in $\N$ defined by:

$L_0 = 4, L_{n+1} = \left({L_n^2 - 2}\right) \bmod\, \left({2^q - 1}\right)$.

Then $2^q - 1$ is prime iff $L_{q-2} = 0$.

Proof

Consider the sequences:

• $U_0 = 0, U_1 = 1, U_{n+1} = 4 U_n - U_{n-1}$;
• $V_0 = 2, V_1 = 4, V_{n+1} = 4 V_n - V_{n-1}$.

The following eqns can be proved by induction:

\((1):\)	\(\displaystyle \)	\(\displaystyle V_n\)	\(=\)	\(\displaystyle U_{n+1} - U_{n-1}\)	\(\displaystyle \)
\((2):\)	\(\displaystyle \)	\(\displaystyle U_n\)	\(=\)	\(\displaystyle \frac {\left({2 + \sqrt 3}\right)^n - \left({2 - \sqrt 3}\right)^n} {\sqrt {12} }\)	\(\displaystyle \)
\((3):\)	\(\displaystyle \)	\(\displaystyle V_n\)	\(=\)	\(\displaystyle \left({2 + \sqrt 3}\right)^n + \left({2 - \sqrt 3}\right)^n\)	\(\displaystyle \)
\((4):\)	\(\displaystyle \)	\(\displaystyle U_{m+n}\)	\(=\)	\(\displaystyle U_m U_{n+1} - U_{m-1} U_n\)	\(\displaystyle \)

Now, let $p$ be prime and $e \ge 1$.

Suppose $U_n \equiv 0 \left({\bmod\, p^{e}}\right)$.

Then $U_n = b p^e$ for some $b$.

Let $U_{n+1} = a$.

By the recurrence relation and $(4)$, we have:

	\(\displaystyle \)	\(\displaystyle U_{2 n}\)	\(=\)	\(\displaystyle b p^e \left({2 a - 4 b p^e}\right) \equiv 2 a U_n\)	\(\displaystyle \left({\bmod\, p^{e+1} }\right)\)
	\(\displaystyle \)	\(\displaystyle U_{2n+1}\)	\(=\)	\(\displaystyle U_{n+1}^2 - U_n^2 \equiv a^2\)	\(\displaystyle \left({\bmod\, p^{e+1} }\right)\)

Similarly:

	\(\displaystyle \)	\(\displaystyle U_{3 n}\)	\(=\)	\(\displaystyle U_{2n+1} U_n - U_{2 n} U_{n-1} \equiv 3 a^2 U_n\)	\(\displaystyle \left({\bmod\, p^{e+1} }\right)\)
	\(\displaystyle \)	\(\displaystyle U_{3n+1}\)	\(=\)	\(\displaystyle U_{2n+1} U_{n+1} - U_{2 n} U_n \equiv a^3\)	\(\displaystyle \left({\bmod\, p^{e+1} }\right)\)

In general:

	\(\displaystyle \)	\(\displaystyle U_{k n}\)	\(\equiv\)	\(\displaystyle k a^{k-1} U_n\)	\(\displaystyle \left({\bmod\, p^{e+1} }\right)\)
	\(\displaystyle \)	\(\displaystyle U_{kn+1}\)	\(\equiv\)	\(\displaystyle a^k\)	\(\displaystyle \left({\bmod\, p^{e+1} }\right)\)

Taking $k = p$, we get:

\((5):\)

\(\displaystyle \)

\(\displaystyle U_n \equiv 0 \left({\bmod\, p^{e} }\right)\)

\(\implies\)

\(\displaystyle U_{n p} \equiv 0\)

\(\displaystyle \left({\bmod\, p^{e+1} }\right)\)

Expanding $\left({2 \pm \sqrt 3}\right)^n$ by the Binomial Theorem, we find that $(2)$ and $(3)$ give us:

	\(\displaystyle \)	\(\displaystyle U_n\)	\(=\)	\(\displaystyle \sum_k \binom n {2 k + 1} 2^{n - 2 k - 1} 3^k\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle V_n\)	\(=\)	\(\displaystyle \sum_k \binom n {2 k} 2^{n - 2 k + 1} 3^k\)	\(\displaystyle \)

Let us set $n = p$ where $p$ is an odd prime.

Then we note that $\binom p k$ is a multiple of $p$ except when $k = 0$ or $k = p$ from Binomial Coefficient of Prime.

We find that:

	\(\displaystyle \)	\(\displaystyle U_p\)	\(\equiv\)	\(\displaystyle 3^{\frac {p-1}2}\)	\(\displaystyle \left({\bmod\, p}\right)\)
	\(\displaystyle \)	\(\displaystyle V_p\)	\(\equiv\)	\(\displaystyle 4\)	\(\displaystyle \left({\bmod\, p}\right)\)

If $p \ne 3$, then from Fermat's Little Theorem we have $3^{p-1} \equiv 1 \left({\bmod\, p}\right)$.

Hence:

• $\left({3^{\frac {p-1}2} - 1}\right) \times \left({3^{\frac {p-1}2} + 1}\right) \equiv 0 \left({\bmod\, p}\right)$;
• $3^{\frac {p-1}2} \equiv \pm 1 \left({\bmod\, p}\right)$.

When $U_p \equiv -1 \left({\bmod\, p}\right)$, we have $U_{p+1} = 4 U_p - U_{p-1} = 4 U_p + V_p - U_{p+1} \equiv -U_{p+1} \left({\bmod\, p}\right)$.

Hence $U_{p+1} \equiv 0 \left({\bmod\, p}\right)$.

When $U_p \equiv +1 \left({\bmod\, p}\right)$, we have $U_{p-1} = 4 U_p - U_{p+1} = 4 U_p - V_p - U_{p-1} \equiv -U_{p-1} \left({\bmod\, p}\right)$.

Hence $U_{p-1} \equiv 0 \left({\bmod\, p}\right)$.

Thus we have shown that:

$(6) \quad \forall p \in \mathbb{P}: \exists \epsilon \left({p}\right): U_{p + \epsilon \left({p}\right)} \equiv 0 \left({\bmod\, p}\right)$

where $\epsilon \left({p}\right)$ is an integer such that $\left|{\epsilon \left({p}\right)}\right| \le 1$.

Now, let $N \in \N$.

Let $m \in \N$ such that $m \left({N}\right)$ is the smallest positive integer such that $U_{m \left({N}\right)} \equiv 0 \left({\bmod\, N}\right)$.

Let $a = U_{m+1} \left({\bmod\, N}\right)$.

Then $a \perp N$ because $\gcd \left\{{U_n, U_{n+1}}\right\} = 1$.

Hence the sequence $U_m, U_{m+1}, U_{m+2}, \ldots$ is congruent modulo $N$ to $a U_0, a U_1, a U_2, \ldots$.

Then we have:

$(7) \quad U_n \equiv 0 \left({\bmod\, N}\right) \iff n = k m \left({N}\right)$ for some integral $k$.

(This number $m \left({N}\right)$ is called the rank of apparition of $N$ in the sequence.)

Now, we have defined the sequence $\left \langle {L_n} \right \rangle$ as $L_0 = 4, L_{n+1} = \left({L_n^2 - 2}\right) \bmod\, \left({2^q - 1}\right)$.

By induction it follows that:

$L_n \equiv V_{2^n} \bmod\, \left({2^q - 1}\right)$.

We have the identity $2 U_{n+1} = 4 U_n + V_n$.

So any common factor of $U_n$ and $V_n$ must divide $U_n$ and $2 U_{n+1}$.

As $U_n \perp U_{n+1}$, this implies that $\gcd \left\{{U_n, V_n}\right\} \le 2$.

So $U_n$ and $V_n$ have no odd factor in common.

So, if $L_{q-2} = 0$, we must have:

	\(\displaystyle \)	\(\displaystyle U_{2^{q-1} } = U_{2^{q-2} } V_{2^{q-2} }\)	\(\equiv\)	\(\displaystyle 0\)	\(\displaystyle \bmod\, \left({2^q - 1}\right)\)
	\(\displaystyle \)	\(\displaystyle U_{2^{q-2} }\)	\(\not \equiv\)	\(\displaystyle 0\)	\(\displaystyle \bmod\, \left({2^q - 1}\right)\)

Now, if $m = m \left({2^q - 1}\right)$ is the rank of apparition of $2^q - 1$, it must be a divisor of $2^{q - 1}$ but not of $2^{q - 2}$. So $m = 2^{q - 1}$.

Now we prove that $n = 2^q - 1$ must therefore be prime.

Let the prime decomposition of $n$ be $p_1^{e_1} \ldots p_r^{e_r}$.

All primes $p_j$ are greater than $3$ because $n$ is odd and congruent to $\left({-1}\right)^q - 1 = -2 \left({\bmod\, 3}\right)$.

From $(5), (6), (7)$ we know that $U_t \equiv 0 \left({\bmod\, 2^q - 1}\right)$, where:

$t = \operatorname {lcm} \left\{{p_1^{e_1-1} \left({p_1 + \epsilon_1}\right), \ldots, p_r^{e_r-1} \left({p_r + \epsilon_r}\right)}\right\}$

where each $\epsilon_j = \pm 1$.

It follows that $t$ is a multiple of $m = 2^{q-1}$.

Let $n_0 = \prod_{j=1}^r p_j^{e_j - 1} \left({p_j + \epsilon_j}\right)$.

We have $n_0 \le \prod_{j=1}^r p_j^{e_j - 1} \left({p_j + \frac {p_j} 5}\right) = \left({\frac 6 5}\right)^r n$.

Also, because $p_j + \epsilon_j$ is even, $t \le \frac {n_0} {2^{r-1}}$, because a factor of $2$ is lost every time the LCM of two even numbers is taken.

Combining these results, we have:

$m \le t \le 2 \left({\frac 3 5}\right)^r n \le 4 \left({\frac 3 5}\right)^r m < 3 m$.

Hence $r \le 2$ and $t = m$ or $t = 2 m$, a power of $2$.

Therefore $e_1 = 1$ and $e_r = 1$.

If $n$ is not prime, we must have $n = 2^q - 1 = \left({2^k + 1}\right) \left({2^l - 1}\right)$ where $\left({2^k + 1}\right)$ and $\left({2^l - 1}\right)$ are prime.

When $q$ is odd, that last factorization is obviously impossible, so $n$ is prime.

Conversely, suppose $n = 2^q - 1$ is prime.

We need to show that $V_{2^{q-2}} \equiv 0 \left({\bmod\, n}\right)$.

All we need to do is show $V_{2^{q-1}} \equiv -2 \left({\bmod\, n}\right)$ because $V_{2^{q-1}} = \left({V_{2^{q-2}}}\right)^2 - 2$.

Now:

	\(\displaystyle \)	\(\displaystyle V_{2^{q-1} }\)	\(=\)	\(\displaystyle \left({\frac {\sqrt 2 + \sqrt 6} 2}\right)^{n+1} + \left({\frac {\sqrt 2 - \sqrt 6} 2}\right)^{n+1}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{-n} \sum_k \binom {n+1} {2k} \sqrt 2^{n+1-2k} \sqrt 6^{2k}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{\frac {1-n} 2} \sum_k \binom {n+1} {2k} 3k\)	\(\displaystyle \)

Since $n$ is an odd prime, the binomial coefficient:

$\displaystyle \binom {n+1}{2k} = \binom {n}{2k} + \binom {n}{2k - 1}$

is divisible by $n$ except when $2k = 0$ and $2k = n+1$, from Binomial Coefficient of Prime.

Hence:

$2^{\frac{n-1}2} V_{2^{q-1}} \equiv 1 + 3^{\frac {n+1}2} \left({\bmod\, n}\right)$.

Here $2 \equiv \left({2^{\frac{q+1}2}}\right)^2$ so $2^{\frac{n-1}2} \equiv \left({2^{\frac{q+1}2}}\right)^{n-1} \equiv i$ by Fermat's Little Theorem.

Finally, by the Law of Quadratic Reciprocity, $3^{\frac{n-1}2} \equiv -1$ since $n \bmod\, 3 = 1$ and $n \bmod\, 4 = 3$.

This means $V_{2^{q-1}} \equiv -2$.

Hence $V_{2^{q-2}} \equiv 0$ as required.

$\blacksquare$

Note

This calculation is particularly suited to binary digital computers, since calculation $\bmod\, \left({2^q - 1}\right)$ is very convenient.

Thus we have a relatively quick way to determine the primality of Mersenne numbers.

Source of Name

This entry was named for Édouard Lucas and Derrick Henry Lehmer.