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

About Brent

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

View all posts by Brent →

5 Responses to MaBloWriMo 23: contradiction!

chushogilionhawk says:

November 24, 2015 at 9:17 am

I’d like to see some posts about ordinal numbers. I find them difficult.
- Brent says:
  
  November 25, 2015 at 8:08 am
  
  Oh, that’s a nice idea!
janhrcek says:

November 24, 2015 at 9:43 am

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?
- Brent says:
  
  November 25, 2015 at 8:08 am
  
  Hmm, good idea!
Pingback: MaBloWriMo 24: Bezout’s identity | The Math Less Traveled

Comments are closed.