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.
Pingback: MaBloWriMo 7: s via omega | The Math Less Traveled