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.!