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!


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.

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

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, arithmetic, computation, number theory, primes and tagged , , , , , , , . Bookmark the permalink.

1 Response to MaBloWriMo 6: The Proof Begins

  1. Pingback: MaBloWriMo 7: s via omega | The Math Less Traveled

Comments are closed.