MaBloWriMo 23: contradiction!

So, where are we? We assumed that s_{n-2} is divisible by M_n, but M_n is not prime. We picked a divisor q of M_n and used it to define a group X^*, and yesterday we showed that \omega has order 2^n in X^*. Today we’ll use this to derive a contradiction.

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

X = \{ a + b\sqrt 3 \mid a, b \in \mathbb{Z}; 0 \leq a, b < q \}.

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

So what about the order of X^*? We got X^* by throwing away elements from X without an inverse. At least we know that 0 doesn’t have an inverse. There might be more, depending on q, but at least we can say that |X^*| \leq q^2 - 1.

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

|X^*| \leq q^2 - 1 \leq M_n - 1 < M_n + 1 = 2^n = |\omega|

The order of the group |X^*| is less than the order of |\omega|! This is a contradiction. So, our assumption that M_n has a nontrivial divisor q must be wrong—M_n is prime!

It took 23 posts, but we have finally proved one direction of the Lucas-Lehmer test: if computing s_{n-2} yields something divisible by M_n, then M_n 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 s_{n-2} is divisible by M_n, then M_n is prime), but it is possible to also prove the converse, that the Lucas-Lehmer test identifies all the Mersenne primes (if M_n is prime, then s_{n-2} will be divisible by M_n). 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.!

Advertisements

About Brent

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

5 Responses to MaBloWriMo 23: contradiction!

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

  2. janhrcek says:

    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?

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

Comments are closed.