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.
- We defined and ; the Lucas-Lehmer test says that is prime if and only if is divisible by . Currently, we’re trying to prove the backwards direction: if is divisible by , then is prime.
- We defined and , and proved that , and .
- 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 then the order of divides .
We’re now going to start the proof proper, which will be a proof by contradiction. So we will assume that is divisible by , but is not prime. From there:
- We will define a group that contains and as elements. The group will be defined in terms of a nontrivial divisor of .
- Using the facts we proved about groups, and the fact that divides , we will show that the order of has to be .
- Finally, we will show that the order of the group has to be less than —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 .