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!
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.
About Brent
Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
Pingback: MaBloWriMo 7: s via omega | The Math Less Traveled