## MaBloWriMo 6: The Proof Begins

Today we’re going to start in on proving the Lucas-Lehmer test. Yesterday we saw how, given a Mersenne number $M_n = 2^n - 1$, we can define a sequence of integers $s_0, s_1, \dots$, with the claim that $s_{n-2} = 0$ if and only if $M_n$ is prime. We’re going to start by focusing on the proof of the “only if” direction, that is, if $s_{n-2} = 0$, then $M_n$ is prime. Once we prove this, we’ll know for sure that the Lucas-Lehmer test produces no false positives: if it says $M_n$ is prime, then it definitely is. Proving the converse—if $M_n$ is prime, then $s_{n-2} = 0$—would mean that the test doesn’t miss any primes. That proof is a bit harder; we’ll see how far we get this month!

I’ll mostly be following Bruce (1993), which is in turn based on Rosen (1988). As is my habit, I’ll expand quite a bit, filling in missing details and exploring interesting tangents as we go.

# And so it begins

Define $\omega = 2 + \sqrt{3}$ and $\overline{\omega} = 2 - \sqrt{3}$. We can easily check that $\omega \overline\omega = 1$:

$\omega \overline\omega = (2 + \sqrt{3})(2 - \sqrt{3}) = 4 - 2\sqrt{3} + 2\sqrt{3} - 3 = 1$.

So what on earth do $\omega$ and $\overline{\omega}$ have to do with the Lucas-Lehmer test? Well, here’s a challenge for you: prove that

$s_m = \omega^{2^m} + \overline{\omega}^{2^m} \pmod{M_n}$.

where $s_m$ are the numbers we defined yesterday. (Hint: use induction on $m$.) Solution to come tomorrow!

# References

Bruce, J. W. 1993. “A Really Trivial Proof of the Lucas-Lehmer Test.” The American Mathematical Monthly 100 (4). Mathematical Association of America: 370–71. http://www.jstor.org/stable/2324959.

Rosen, Michael I. 1988. “A Proof of the Lucas-Lehmer Test.” Am. Math. Monthly 95 (9). Washington, DC, USA: Mathematical Association of America: 855–56. doi:10.2307/2322904.