MaBloWriMo 17: X marks the spot

Recall that we are trying to prove that if s_{n-2} is divisible by M_n, then M_n is prime. So let’s suppose s_{n-2} is divisible by M_n. We’ll prove this by contradiction, so suppose M_n is not prime: if we can derive a contradiction, then this assumption must have been incorrect.

If M_n is not prime then it must have some nontrivial divisors. Note that divisors of any number a always come in pairs that multiply to the given number, rs = a. If a is a perfect square then the two divisors might be equal, but in general one divisor will be smaller than \sqrt a and one will be bigger. In any case, we know we can pick some divisor of M_n, call it q, such that q^2 \leq M_n.1

Now define the set X as follows:

X = \{ a + b \sqrt 3 \mid a,b \in \mathbb{Z}; 0 \leq a,b < q \}.

That is, X is the set of all things of the form a + b\sqrt 3 where a and b are both integers between 0 (inclusive) and q (exclusive). So (assuming q is big enough) X contains things like 5 + 6 \sqrt{3} and 1 + 2 \sqrt 3 and 6 (just set b = 0) and 2 \sqrt 3 (set a = 0). And, yes, you guessed it, X also contains \omega = 2 + \sqrt 3. It doesn’t seem to contain \overline{\omega} = 2 - \sqrt{3}, but we’ll see in a minute that it actually sorta kinda does.

We now introduce a binary operation on elements of X, which we want to be like multiplication. But if we just multiply two elements of X in the obvious way we won’t necessarily end up with something in X: the resulting coefficients a and b might be too big. So the operation we actually introduce is this: multiply in the usual way, and then at the end reduce the coefficients a and b \pmod q. For example, if q = 5 then

(1 + 2 \sqrt{3})(3 + 4 \sqrt{3}) = 3 + 4 \sqrt 3 + 6 \sqrt{3} + 8 \cdot 3 = 27 + 10 \sqrt{3} = 2 + 0 \sqrt{3} = 2.

That is, we distribute out the product and collect up like terms, resulting in 27 + 10 \sqrt{3}, and then take the remainder of both 27 and 10 when divided by 5.

Since we are considering coefficients equivalent \pmod q, we can say that X does contain \overline{\omega} in a sense, since 2 - \sqrt{3} = 2 + (q-1)\sqrt{3}. Indeed, we can check that

\omega \overline{\omega} = (2 + \sqrt{3})(2 + (q-1)\sqrt{3}) = (1 + 3q) + 2q \sqrt{3} = 1.

So this representation of \overline{\omega} still interacts with \omega in the right way.

So, is X a group? I’ll let you think about it until tomorrow!


Bruce, J. W. 1993. “A Really Trivial Proof of the Lucas-Lehmer Test.” The American Mathematical Monthly 100 (4). Mathematical Association of America: 370–71.

  1. Bruce (1993) specifies that q should be prime, but I cannot see what difference it makes. In any case we can easily ensure that q is prime, if necessary.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, arithmetic, group theory, number theory and tagged , , , , . Bookmark the permalink.

3 Responses to MaBloWriMo 17: X marks the spot

  1. groupy says:

    Thanks for the interesting blog series. Today’s post has a bunch of “latex path not specified” scattered throughout the page. It doesn’t occur for every “img src” request?

    • Brent says:

      I noticed that in the feed. I’m not sure what’s going on there. However, if I view the post in my browser on itself, all the equations display correctly for me. Are you still seeing “latex path not specified” when you view it directly on the site?

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

Comments are closed.