Today we’re going to start in on proving the Lucas-Lehmer test. Yesterday we saw how, given a Mersenne number , we can define a sequence of integers , with the claim that if and only if is prime. We’re going to start by focusing on the proof of the “only if” direction, that is, if , then is prime. Once we prove this, we’ll know for sure that the Lucas-Lehmer test produces no false positives: if it says is prime, then it definitely is. Proving the converse—if is prime, then —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 and . We can easily check that :
So what on earth do and have to do with the Lucas-Lehmer test? Well, here’s a challenge for you: prove that
where are the numbers we defined yesterday. (Hint: use induction on .) Solution to come tomorrow!
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.