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

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.

• Brent says:

Oh, that’s a nice idea!

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?

• Brent says:

Hmm, good idea!