## 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$. 