So, where are we? We assumed that is divisible by , but is *not* prime. We picked a divisor of and used it to define a group , and yesterday we showed that has order in . Today we’ll use this to derive a contradiction.

Recall that we picked so that —we can always pick a divisor of that is less than (or equal to) the square root of . We then defined in terms of as

.

So how many elements are in the set ? That’s not too hard: there are choices for the coefficient , and choices for the coefficient ; each pair of choices gives a different element of , which therefore contains elements.

So what about the order of ? We got by throwing away elements from without an inverse. At least we know that doesn’t have an inverse. There might be more, depending on , but at least we can say that .

is in the group , and we showed that the order of an element cannot exceed the order of the group. But, check this out:

The order of the group is less than the order of ! This is a contradiction. So, our assumption that has a nontrivial divisor must be wrong— is prime!

It took 23 posts, but we have finally proved one direction of the Lucas-Lehmer test: if computing yields something divisible by , then is definitely prime.

And now I have to decide what to do with the remaining week. Of course, there is another direction to prove: we have only shown that the Lucas-Lehmer test correctly identifies primes (if is divisible by , then is prime), but it is possible to also prove the converse, that the Lucas-Lehmer test identifies *all* the Mersenne primes (if is prime, then will be divisible by ). I am still trying to figure out how difficult this proof is. I don’t think we’ll be able to fit it in the last 7 days of the month, but it still might be worth starting it and finishing it on a more relaxed schedule.

Of course, I’m also open to questions, suggestions, *etc.*!

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

I’d like to see some posts about ordinal numbers. I find them difficult.

Oh, that’s a nice idea!

I’ve been watching your MaBloWriMo posts since the beginning. Good job explaining the proof! I have a suggestion for the following week: what about proving Lagrange’s theorem?

Hmm, good idea!

Pingback: MaBloWriMo 24: Bezout’s identity | The Math Less Traveled