lucas lehmer test.

Question

I asked to use the Lucas_Lehmer test to show that $2^{11} -1$ is prime i was wondering if there are any by hand examples of someone using this test on a mersenne prime that anyone knows of.

I tried googling the test but the explanation in itself confused me so i was hoping to see an example not just a explanation of what the test is. ( i realize this test was intended for computers to be programmed to test primes but i would like to see an example by hand.)

Answer 1

To give an example, let's take $127$. Then, the algorithm asks us to do the following:

• Set $s = 4$, step zero.
• $s \to s^2 - 2\mod 127 = 14$, step one.
• $s \to s^2 - 2\mod 127 = 194 \mod 127 = 67$, step two.
• $s \to s^2 - 2\mod 127 = 4487 \mod 127 = 42$, step three.
• $s \to s^2 - 2\mod 127 = 1762 \mod 127 = 111$, step four.
• $s \to s^2 - 2\mod 127 = 12319 \mod 127 = 0$, step five ($= 7 - 2$).

Since $s_5 \equiv 0 \mod 127$, we see that $127$ is a prime number.

Answer 2

We define a sequence $s_i$ such that $s_0=4$ and $s_{i+1} = s_i^2 - 2$, and check whether $s_{11-2} \equiv 0 \pmod{2^{11}-1}$.

• $s_0 \equiv 4$
• $s_1 \equiv 4^2 - 2 \equiv 14$
• $s_2 \equiv 14^2 - 2 \equiv 194$
• $s_3 \equiv 194^2 - 2 \equiv 788$
• $s_4 \equiv 788^2 - 2 \equiv 701$
• $s_5 \equiv 701^2 - 2 \equiv 119$
• $s_6 \equiv 119^2 - 2 \equiv 1877$
• $s_7 \equiv 1877^2 - 2 \equiv 240$
• $s_8 \equiv 240^2 - 2 \equiv 282$
• $s_9 \equiv 282^2 - 2 \equiv 1736$

Therefore $2^{11} - 1$ is not prime.

(Note: $2^{11} - 1 = 2047 = 23 \times 89$.)