MaBloWriMo 16: Recap and outline

We have now established all the facts we will need about groups, and have incidentally just passed the halfway point of MaBloWriMo. This feels like a good time to take a step back and outline what we’ve done so far and where we are going.

So far:

We defined $s_0 = 4$ and $s_n = s_{n-1}^2 - 2$ ; the Lucas-Lehmer test says that $M_n = 2^n - 1$ is prime if and only if $s_{n-2}$ is divisible by $M_n$ . Currently, we’re trying to prove the backwards direction: if $s_{n-2}$ is divisible by $M_n$ , then $M_n$ is prime.
We defined $\omega = 2 + \sqrt 3$ and $\overline{\omega} = 2 - \sqrt 3$ , and proved that $\omega \overline{\omega} = 1$ , and $s_m = \omega^{2^m} + \overline{\omega}^{2^m}$ .
We learned the definition of groups, looked at some examples, and proved some simple facts, such as:
- Every element of a finite group has a finite order.
- The order of an element is at most the size of the group.
- If $g^n = e$ then the order of $g$ divides $n$ .

We’re now going to start the proof proper, which will be a proof by contradiction. So we will assume that $s_{n-2}$ is divisible by $M_n$ , but $M_n$ is not prime. From there:

We will define a group that contains $\omega$ and $\overline{\omega}$ as elements. The group will be defined in terms of a nontrivial divisor of $M_n$ .
Using the facts we proved about groups, and the fact that $M_n$ divides $s_{n-2}$ , we will show that the order of $\omega$ has to be $2^n$ .
Finally, we will show that the order of the group has to be less than $2^n$ —a contradiction, since the order of elements is never greater than the order of the group.

Tomorrow: we’ll start in on defining the crucial group that contains $\omega$ .

About Brent

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

View all posts by Brent →