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

  1. Pingback: MaBloWriMo 20: the group X star | The Math Less Traveled

  2. Pingback: MaBloWriMo 21: the order of omega, part I | The Math Less Traveled

Comments are closed.