Alternate Lucas-Lehmer Seed

For any $s_0$ , if $\frac{1}{4}s_0^2 - 1$ is not a perfect square, and $(\frac{1}{2}s_0 - 1)^{\frac{1}{2}(M - 1)} \equiv 1 \pmod{M}$ for any Mersenne prime $M$ , and $(\frac{1}{2}s_0 + 1)^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ for any Mersenne prime $M$ , then $s_0$ can be used as a seed for the primality test in which for any prime number $p > 2$ , Mersenne prime $M_p = 2^{p} - 1$ is also prime if and only if $a_{p - 2} \equiv 0 \pmod {M_p}$ for the recursive sequence $a_n = a_{n - 1}^2 - 2$ , starting with $a_0 = s_0$ (see proof below).

Typically, the $a_0$ seed that is used in the Lucas-Lehmer primality test is $s_0 = 4$ , because:

$1)\hspace{0.25cm}\frac{1}{4}s_0^2 - 1 = 3$ is not a perfect square.

$2)\hspace{0.25cm}(\frac{1}{2}s_0 - 1)^{\frac{1}{2}(M - 1)} = 1^{\frac{1}{2}(M - 1)} = 1 \equiv 1 \pmod{M}$ for any Mersenne prime $M$ .

$3)\hspace{0.25cm}(\frac{1}{2}s_0 + 1)^{\frac{1}{2}(M - 1)} = 3^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ for any Mersenne prime $M$ .

$\hspace{2cm}$ $2^{2n+1} - 1 \equiv 7 \pmod{12}$ for all positive integers of $n$ by induction:

$\hspace{3cm}$ $2^{2 \cdot 1+1} - 1 = 2^3 - 1 = 7 \equiv 7 \pmod{12}$

$\hspace{3cm}$ Assuming $2^{2n+1} - 1 \equiv 7 \pmod{12}$ :

$\hspace{4cm}$ then $2^{2n+1} \equiv 8 \pmod{12}$

$\hspace{4cm}$ so $2^{2(n+1)+1} - 1 = 2^{2n+3} - 1 = 2^{2n+1}2^2 - 1 \equiv 8 \cdot 4 - 1 \equiv 7 \pmod{12}$

$\hspace{2cm}$ Since $p$ is a prime larger than $2$ , $p = 2n + 1$ for all positive integers,

$\hspace{3cm}$ so $M = 2^p - 1 = 2^{2n + 1} - 1 \equiv 7 \pmod{12}$ .

$\hspace{2cm}$ Since $M \equiv 7 \pmod{12}$ , $M = 12k + 7$ for some integer $k$

$\hspace{2cm}$ by the law of quadratic reciprocity , $(3 | 12k + 7)(12k + 7 | 3)$ .

$\hspace{3cm}$ $= (-1)^{\frac{1}{2}(3 - 1)\frac{1}{2}(12k + 7 - 1)} = (-1)^{6k + 3} = -1$ .

$\hspace{2cm}$ Now, $(12k + 7 | 3) = (3 \cdot 4k + 3 \cdot 2 + 1 | 3) \equiv (1 | 3) = 1$

$\hspace{2cm}$ so $(3 | 12k + 7) = -1$ .

$\hspace{2cm}$ or $(3 | M) = -1$ , which means $3$ is a quadratic nonresidue of $M$ .

$\hspace{2cm}$ So by Euler’s criterion, $3^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ .

However, there are other $a_0$ values that satisfy the above criteria as well. Since we know that $M_3 = 2^3 - 1 = 7$ is a Mersenne prime for $p = 3$ , then for a test to be true with a different $a_0$ seed we must have that $a_{p - 2} \equiv 0 \pmod {M_p}$ , or in this case, $a_1 \equiv 0 \pmod {7}$ . In other words, $a_0^2 - 2$ must be divisible by $7$ . We can numerically eliminate $5$ , $6$ , $7$ , $8$ , and $9$ as possible $s_0$ values as none of these give an $a_0^2 - 2$ value that is divisible by $7$ , but $a_0 = 10$ is the next possible candidate as $a_0^2 - 2 = 10^2 - 2 = 98$ , which is divisible by $7$ .

Indeed, we find that $s_0 = 10$ also satisfies the above criteria as well:

$1)\hspace{0.25cm}\frac{1}{4}s_0^2 - 1 = 24$ is not a perfect square.

$2)\hspace{0.25cm}(\frac{1}{2}s_0 - 1)^{\frac{1}{2}(M - 1)} = 4^{\frac{1}{2}(M - 1)} \equiv 1 \pmod{M}$ for any Mersenne prime $M$ :

$\hspace{2cm}$ $4^{\frac{1}{2}(M - 1)} = (2^2)^{\frac{1}{2}(M - 1)} = 2^{M - 1}$ ,

$\hspace{2cm}$ and $2^{M - 1} \equiv 1 \pmod{M}$ by Fermat's Little Theorem .

$3)\hspace{0.25cm}(\frac{1}{2}s_0 + 1)^{\frac{1}{2}(M - 1)} = 6^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ for any Mersenne prime $M$ :

$\hspace{2cm}$ Since $M = 2^p - 1$ , $2^{\frac{1}{2}(M - 1)} = 2^{\frac{1}{2}((2^p - 1) - 1)} = 2^{2^{p - 1} - 1}$ .

$\hspace{2cm}$ By Fermat's Little Theorem , $2^{p - 1} - 1 = kp$ for some integer $k$ , so $2^{2^{p - 1} - 1} = 2^{kp} = (2^p)^k$ .

$\hspace{2cm}$ Since $2^p \equiv 1 \pmod{2^p - 1}$ , $(2^p)^k \equiv 1^k = 1 \pmod{2^p - 1 = M}$ ,

$\hspace{2cm}$ and so $2^{\frac{1}{2}(M - 1)} \equiv 1 \pmod{M}$ .

$\hspace{2cm}$ From above, we have $3^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ .

$\hspace{2cm}$ Therefore, $6^{\frac{1}{2}(M - 1)} = (2^{\frac{1}{2}(M - 1)})(3^{\frac{1}{2}(M - 1)}) \equiv (1)(-1) = -1 \pmod{M}$ .

Therefore, the next positive integer greater than $4$ that can also be used as $a_0$ in the primality test is $s_0 = \boxed{10}$ .

---

Prove:

For any $s_0$ , if $\frac{1}{4}s_0^2 - 1$ is not a perfect square, and $(\frac{1}{2}s_0 - 1)^{\frac{1}{2}(M - 1)} \equiv 1 \pmod{M}$ for any Mersenne prime $M$ , and $(\frac{1}{2}s_0 + 1)^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ for any Mersenne prime $M$ , then $s_0$ can be used as a seed for the primality test in which for any prime number $p > 2$ , Mersenne prime $M_p = 2^{p} - 1$ is also prime if and only if $s_{p - 2} \equiv 0 \pmod {M_p}$ for the recursive sequence $s_n = a_{n - 1}^2 - 2$ , starting with $a_0 = s_0$ .

$\hspace{1cm}$

Given:

$\frac{1}{4}s_0^2 - 1$ is not a perfect square

$(\frac{1}{2}s_0 - 1)^{\frac{1}{2}(M - 1)} \equiv 1 \pmod{M}$ for any Mersenne prime $M$

$(\frac{1}{2}s_0 + 1)^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ for any Mersenne prime $M$

$\hspace{1cm}$

Definitions:

Let $a = \frac{1}{2}s_0$

Let $b = a^2 - 1$

Let $u = a + \sqrt{b}$

Let $\overline{u} = a - \sqrt{b}$

Then $u\overline{u} = (a + \sqrt{b})(a - \sqrt{b}) = a^2 - b = a^2 - (a^2 - 1) = 1$

And $s_n = u^{2^n} + \overline{u}^{2^n}$ by induction:

$\hspace{1cm}s_0 = u^{2^0} + \overline{u}^{2^0} = u + \overline{u} = (a + \sqrt{b}) + (a - \sqrt{b}) = 2a = 2 \cdot \frac{1}{2}s_0 = s_0$

$\hspace{1cm}$ Assuming $s_n = u^{2^n} + \overline{u}^{2^n}$ :

$\hspace{2cm}s_{n+1} = s_n^2 - 2$

$\hspace{2cm}s_{n+1} = (u^{2^n} + \overline{u}^{2^n})^2 - 2$

$\hspace{2cm}s_{n+1} = u^{2 \cdot 2^n} + 2u^{2^n}\overline{u}^{2^n} + \overline{u}^{2 \cdot 2^n} - 2$

$\hspace{2cm}s_{n+1} = u^{2^{n + 1}} + 2(u\overline{u})^{2^n} + \overline{u}^{2^{n + 1}} - 2$

$\hspace{2cm}s_{n+1} = u^{2^{n + 1}} + 2(1)^{2^n} + \overline{u}^{2^{n + 1}} - 2$

$\hspace{2cm}s_{n+1} = u^{2^{n + 1}} + \overline{u}^{2^{n + 1}}$

$\hspace{1cm}$

Proof of Sufficiency:

Prove: If $s_{p - 2}$ is divisible by $2^{p} - 1$ , then $2^{p} - 1$ is a prime number.

Assume $s_{p - 2}$ is divisible by $2^{p} - 1$ :

$\hspace{1cm}$ Let $M = 2^{p} - 1$

$\hspace{1cm}$ $s_{p - 2} = kM$ for some integer $k$

$\hspace{1cm}$ $u^{2^{p - 2}} + \overline{u}^{2^{p - 2}} = kM$

$\hspace{1cm}$ $u^{2^{p - 2}} = kM - \overline{u}^{2^{p - 2}}$

$\hspace{1cm}$ $u^{2^{p - 2}}u^{2^{p - 2}} = kMu^{2^{p - 2}} - \overline{u}^{2^{p - 2}}u^{2^{p - 2}}$

$\hspace{1cm}$ $(u^{2^{p - 2}})^2 = kMu^{2^{p - 2}} - (u\overline{u})^{2^{p - 2}}$

$\hspace{1cm}$ $u^{2^{p - 1}} = kMu^{2^{p - 2}} - 1$

$\hspace{1cm}$ Assume that $2^p - 1$ is not a prime number:

$\hspace{2cm}$ Let $q$ be the smallest prime factor of $M = 2^p - 1$

$\hspace{2cm}$ $M \equiv 0 \pmod q$

$\hspace{2cm}$ $u^{2^{p - 1}} \equiv k \cdot 0 \cdot u^{2^{p - 2}} - 1 \pmod q$

$\hspace{2cm}$ $u^{2^{p - 1}} \equiv -1 \pmod q$

$\hspace{2cm}$ $(u^{2^{p - 1}})^2 \equiv (-1)^2 \pmod q$

$\hspace{2cm}$ $u^{2^p} \equiv 1 \pmod q$

$\hspace{2cm}$ Since $u^{2^{p - 1}} \neq 1$ , the order does not divide $2^{p - 1}$ , so the order is $2^p$

$\hspace{2cm}$ Let $X = \{n + m\sqrt{b} | n, m \in \text{Z}_q\}$ and $X^* = \{$ all elements of $X$ except $0\}$

$\hspace{2cm}$ $|X| = q^2$ and $|X^*| = q^2 - 1$ (as long as $b$ is not a perfect square, which is true by the given criteria of $s_0$ )

$\hspace{2cm}$ $u$ is in $X^*$ , and since the order of an element is at most the order of its size, $2^p \leq q^2 - 1 < q^2$

$\hspace{2cm}$ Since $q$ is the smallest prime factor of $M$ , $q^2 < M = 2^p - 1$

$\hspace{2cm}$ But then $2^p < 2^p - 1$ which is a contradiction.

$\hspace{1cm}$ So $2^p - 1$ must be a prime number.

$\hspace{1cm}$

Proof of Necessity:

Prove: If $2^p - 1$ is a prime number, then $s_{p - 2}$ is divisible by $2^p - 1$ .

$\hspace{1cm}$

If $2^p - 1$ is a prime number, then $p$ must be a prime number: Assume $p$ is not a prime number:

$\hspace{1cm}$ Then $p$ has two factors $m \geq 2$ and $n \geq 2$ such that $p = mn$ .

$\hspace{1cm}$ But then $2^p - 1 = 2^{mn} - 1$ which is divisible by $2^m - 1$ and $2^n - 1$ .

$\hspace{1cm}$ This contradicts the assumption that $2^p - 1$ is a prime number.

$\hspace{1cm}$ So $p$ must be a prime number.

$\hspace{1cm}$

Let $M = 2^p - 1$ .

$\hspace{1cm}$

$u^{\frac{1}{2}(M+1)} \equiv -1 \pmod{M}$ :

$\hspace{1cm}$ Since $u = a + \sqrt{b}$ and $b = a^2 - 1$ , $u = \frac{(a + 1 + \sqrt{b})^2}{2(a + 1)}$

$\hspace{1cm}$ so $u^{\frac{1}{2}(M+1)} = \bigg(\frac{(a + 1 + \sqrt{b})^2}{2(a + 1)}\bigg)^{\frac{1}{2}(M + 1)} \equiv \frac{2(a + 1)}{-2(a + 1)} \pmod M = -1 \pmod M$ :

$\hspace{2cm}$ the numerator $((a + 1 + \sqrt{b})^2)^{\frac{1}{2}(M + 1)} = (a + 1 + \sqrt{b})(a + 1 + \sqrt{b})^M$

$\hspace{3cm}$ using the binomial theorem in a finite field and prime exponent $M$ , $(a + 1 + \sqrt{b})^M \equiv (a + 1)^M + \sqrt{b}^M \pmod M$

$\hspace{3cm}$ and using Fermat’s Little Theorem , $(a + 1)^M \equiv a + 1 \pmod M$

$\hspace{3cm}$ since $b = a^2 - 1$ , $\sqrt{b}^M = (a - 1)^{\frac{1}{2}(M - 1)}(a + 1)^{\frac{1}{2}(M - 1)}\sqrt{b}$

$\hspace{3cm}$ and since by the given criteria $(a - 1)^{\frac{1}{2}(M - 1)} \equiv 1 \pmod{M}$ and $(a + 1)^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$ , $\sqrt{b}^M \equiv (1)(-1)\sqrt{b} = -\sqrt{b} \pmod{M}$

$\hspace{3cm}$ therefore, $(a + 1 + \sqrt{b})^M \equiv (a + 1 - \sqrt{b}) \pmod{M}$

$\hspace{3cm}$ so $(a + 1 + \sqrt{b})(a + 1 + \sqrt{b})^M \equiv (a + 1 + \sqrt{b})(a + 1 - \sqrt{b}) \pmod{M}$ and since $b = a^2 - 1$ , this is equivalent to $2(a + 1) \pmod{M}$

$\hspace{3cm}$ so the numerator $((a + 1 + \sqrt{b})^2)^{\frac{1}{2}(M + 1)} \equiv 2(a + 1) \pmod{M}$

$\hspace{2cm}$ the denominator $(2(a + 1))^{\frac{1}{2}(M + 1)} = 2^{\frac{1}{2}(M - 1)}(a + 1)^{\frac{1}{2}(M - 1)}2(a + 1)$

$\hspace{3cm}$ since $M = 2^p - 1$ , $2^{\frac{1}{2}(M - 1)} = 2^{\frac{1}{2}((2^p - 1) - 1)} = 2^{2^{p - 1} - 1}$ .

$\hspace{3cm}$ by Fermat's Little Theorem , $2^{p - 1} - 1 = kp$ for some integer $k$ , so $2^{2^{p - 1} - 1} = 2^{kp} = (2^p)^k$ .

$\hspace{3cm}$ since $2^p \equiv 1 \pmod{2^p - 1}$ , $(2^p)^k \equiv 1^k = 1 \pmod{2^p - 1 = M}$ ,

$\hspace{3cm}$ and so $2^{\frac{1}{2}(M - 1)} \equiv 1 \pmod{M}$ .

$\hspace{3cm}$ by the given criteria, $(a + 1)^{\frac{1}{2}(M - 1)} \equiv -1 \pmod{M}$

$\hspace{3cm}$ so the denominator $2^{\frac{1}{2}(M - 1)}(a + 1)^{\frac{1}{2}(M - 1)}2(a + 1) \equiv (1)(-1)2(a + 1) = -2(a + 1) \pmod{M}$ .

$\hspace{1cm}$

Since $u^\frac{1}{2}(M+1) \equiv -1 \pmod{M}$ :

$\hspace{1cm}$ $u^{\frac{1}{4}(M+1)}u^{\frac{1}{4}(M+1)} \equiv -1 \pmod{M}$

$\hspace{1cm}$ $u^{\frac{1}{4}(M+1)}u^{\frac{1}{4}(M+1)}\overline{u}^{\frac{1}{4}(M+1)} \equiv -\overline{u}^{\frac{1}{4}(M+1)} \pmod{M}$

$\hspace{1cm}$ $u^{\frac{1}{4}(M+1)}(u\overline{u})^{\frac{1}{4}(M+1)} \equiv -\overline{u}^{\frac{1}{4}(M+1)} \pmod{M}$

$\hspace{1cm}$ $u^{\frac{1}{4}(M+1)}(1)^{\frac{1}{4}(M+1)} \equiv -\overline{u}^{\frac{1}{4}(M+1)} \pmod{M}$

$\hspace{1cm}$ $u^{\frac{1}{4}(M+1)} \equiv -\overline{u}^{\frac{1}{4}(M+1)} \pmod{M}$

$\hspace{1cm}$ $u^{\frac{1}{4}(M+1)} + \overline{u}^{\frac{1}{4}(M+1)} \equiv 0 \pmod{M}$

$\hspace{1cm}$ $u^{\frac{1}{4}((2^p - 1)+1)} + \overline{u}^{\frac{1}{4}((2^p - 1)+1)} \equiv 0 \pmod{M}$

$\hspace{1cm}$ $u^{\frac{1}{4}(2^p)} + \overline{u}^{\frac{1}{4}(2^p)} \equiv 0 \pmod{M}$

$\hspace{1cm}$ $u^{2^{p - 2}} + \overline{u}^{2^{p - 2}} \equiv 0 \pmod{M}$

$\hspace{1cm}$ $s_{p-2} \equiv 0 \pmod M$

$\hspace{1cm}$

Therefore, if $2^p - 1$ is a prime number, then $s_{p - 2}$ is divisible by $2^p - 1$ .

In OEIS,there is a sequence of "Lucas-Lehmer Seeds".View A018844