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

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

### 2 Responses to MaBloWriMo 16: Recap and outline

Comments are closed.