## 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. http://www.jstor.org/stable/2324959.

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.

### 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 mathlesstraveled.com itself, all the equations display correctly for me. Are you still seeing “latex path not specified” when you view it directly on the site?