## MaBloWriMo 24: Bezout’s identity

A few days ago we made use of Bézout’s Identity, which states that if $a$ and $b$ have a greatest common divisor $d$, then there exist integers $x$ and $y$ such that $ax + by = d$. For completeness, let’s prove it.

Consider the set of all linear combinations of $a$ and $b$, that is,

$\{ax + by \mid x, y \in \mathbb{Z} \}$,

and suppose $d = as + bt$ is the smallest positive integer in this set. For example, if $a = 10$ and $b = 6$, then you can check that, for example, $16 = a + b$, and $8 = 2a - 2b$, and $4 = a - b$ are all in this set, as is, for example, $-4 = -a + b$, but the smallest positive integer you can get is $2 = 2a - 3b$. We will prove that in fact, $d$ is the greatest common divisor of $a$ and $b$.

Consider dividing $a$ by $d$. This will result in some remainder $r$ such that $0 \leq r < d$. I claim the remainder is also of the form $ax + by$ for some integers $x$ and $y$: note that $a = a1 + b0$ is of this form, and $d$ is of this form by definition, and we get the remainder by subtracting some number of copies of $d$ from $a$. Subtracting two numbers of the form $ax + by$ works by subtracting coefficients, yielding another number of the same form again. But $d$ is supposed to be the smallest positive number of this form, and $r$ is less than $d$—which means $r$ has to be zero, that is, $d$ evenly divides $a$. The same argument shows that $d$ evenly divides $b$ as well. So $d$ is a common divisor of $a$ and $b$.

To see that $d$ is the greatest common divisor, suppose $c$ also divides $a$ and $b$. Then since $d = ax + by$, we can see that $c$ must divide $d$ as well—so it must be less than or equal to $d$.

Voila! This proof doesn’t show us how to actually compute some appropriate $x$ and $y$ given $a$ and $b$—that can be done using the extended Euclidean algorithm; perhaps I’ll write about that some other time. But this proof will do for today.

For the remainder of the month, as suggested by commented janhrcek, we’ll prove the thing I hinted at in an earlier post: namely, that the order of any group element is always a divisor of the order of the group. This is a really cool proof that hints at some much deeper group theory.

| Tagged , , , , , , | 2 Comments

So, where are we? We assumed that $s_{n-2}$ is divisible by $M_n$, but $M_n$ is not prime. We picked a divisor $q$ of $M_n$ and used it to define a group $X^*$, and yesterday we showed that $\omega$ has order $2^n$ in $X^*$. Today we’ll use this to derive a contradiction.

Recall that we picked $q$ so that $q^2 \leq M_n$—we can always pick a divisor of $M_n$ that is less than (or equal to) the square root of $M_n$. We then defined $X$ in terms of $q$ as

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

So how many elements are in the set $X$? That’s not too hard: there are $q$ choices for the coefficient $a$, and $q$ choices for the coefficient $b$; each pair of choices gives a different element of $X$, which therefore contains $q^2$ elements.

So what about the order of $X^*$? We got $X^*$ by throwing away elements from $X$ without an inverse. At least we know that $0$ doesn’t have an inverse. There might be more, depending on $q$, but at least we can say that $|X^*| \leq q^2 - 1$.

$\omega$ is in the group $X^*$, and we showed that the order of an element cannot exceed the order of the group. But, check this out:

$|X^*| \leq q^2 - 1 \leq M_n - 1 < M_n + 1 = 2^n = |\omega|$

The order of the group $|X^*|$ is less than the order of $|\omega|$! This is a contradiction. So, our assumption that $M_n$ has a nontrivial divisor $q$ must be wrong—$M_n$ is prime!

It took 23 posts, but we have finally proved one direction of the Lucas-Lehmer test: if computing $s_{n-2}$ yields something divisible by $M_n$, then $M_n$ is definitely prime.

And now I have to decide what to do with the remaining week. Of course, there is another direction to prove: we have only shown that the Lucas-Lehmer test correctly identifies primes (if $s_{n-2}$ is divisible by $M_n$, then $M_n$ is prime), but it is possible to also prove the converse, that the Lucas-Lehmer test identifies all the Mersenne primes (if $M_n$ is prime, then $s_{n-2}$ will be divisible by $M_n$). I am still trying to figure out how difficult this proof is. I don’t think we’ll be able to fit it in the last 7 days of the month, but it still might be worth starting it and finishing it on a more relaxed schedule.

Of course, I’m also open to questions, suggestions, etc.!

| Tagged , , , , , , | 5 Comments

## MaBloWriMo 22: the order of omega, part II

Yesterday, from the assumption that $s_{n-2}$ is divisible by $M_n$, we deduced the equations

$\omega^{2^{n-1}} = q-1$

and

$\omega^{2^n} = 1$

which hold in the group $X^*$. So what do these tell us about the order of $\omega$? Well, first of all, the second equation tells us that the order of $\omega$ must be a divisor of $2^n$, and the only divisors of $2^n$ are other powers of $2$. So the order of $\omega$ must be $2^k$ for some $k \leq n$.

Now suppose the order of $\omega$ is $2^k$, so $\omega^{2^k} = 1$. But then if we square both sides we get $\omega^{2^{k+1}} = 1$. Squaring again gives $\omega^{2^{k+2}} = 1$, and so on. So once we hit $1$, we are stuck there: raising $\omega$ to all bigger powers of $2$ will also yield $1$.

But now look at the first equation: $\omega^{2^{n-1}} = q-1$. Remember that the order of $\omega$ has to be a power of $2$. From this equation we can see that the order can’t be $2^{n-1}$. Could it be a smaller power of two? In fact, no, it can’t, by the argument in the previous paragraph: once you hit a power of two that yields $1$, all the higher powers also have to yield $1$. So if $\omega$ raised to any smaller power of $2$ were the identity, then $\omega^{2^{n-1}}$ would also have to be the identity—but it isn’t.

The inescapable conclusion is that the only possibility for the order of $\omega$ is exactly $2^n$.

So, how does that help? Hint: think about the order of the group $X^*$… the triumphant conclusion tomorrow!

| Tagged , , , , , , | 1 Comment

## MaBloWriMo 21: the order of omega, part I

Now we’re going to figure out the order of $\omega$ in the group $X^*$.

Remember that we started by assuming that $M_n$ passed the Lucas-Lehmer test, that is, that $s_{n-2}$ is divisible by $M_n$. Remember that we also showed

$s_m = \omega^{2^m} + \overline{\omega}^{2^m}$

for all $m \geq 0$. In fact, this proof is valid in $X^*$ too, if we take everything $\pmod q$. The proof deals only with $\omega$ and $\overline{\omega}$, integers, and addition and multiplication. We know $\omega$ and $\overline{\omega}$ are in $X^*$, and we know that addition and multiplication can be interchanged with taking remainders. So what about integers like $s_m$? I claim that every nonzero integer (or, in particular, its remainder $\pmod q$) is in $X^*$ as well, if $q$ is prime.1 That is, for every integer $a < q$, there is some other integer $x < q$ such that $ax = 1 \pmod q$. This is because of something called Bézout’s Identity (which I should probably prove in another post, for completeness; it is not hard to prove): if $a$ and $b$ have a greatest common divisor $d$, then there exist integers $x$ and $y$ such that $ax + by = d$. In this case, if $q$ is prime then any nonzero number less than $q$ has a gcd of $1$ with $q$. So by Bézout’s Identity for any $a < q$ there are numbers $x$ and $y$ such that $ax + qy = 1$. Taken $\pmod q$, this says that $ax = 1$.

So our equation for $s_m$ in terms of $\omega$ and $\overline{\omega}$ is valid as an equation in the group $X^*$; from here on all our equations will similarly “live in in $X^*$-world”. We have to take everything $\pmod q$ though. In particular, If $s_{n-2}$ is divisible by $M_n$, then $s_{n-2}$ is also divisible by $q$ (since $q$ divides $M_n$), which means $s_{n-2} = 0$ in $X^*$. Hence

$\omega^{2^{n-2}} + \overline{\omega}^{2^{n-2}} = 0$.

Now we multiply both sides by $\omega^{2^{n-2}}$. First, multiplying $\omega^{2^{n-2}}$ by itself results in an exponent of $2^{n-2} + 2^{n-2} = 2 \cdot 2^{n-2} = 2^{n-1}$. For the other term, $\overline{\omega}^{2^{n-2}} \omega^{2^{n-2}} = (\overline{\omega} \omega)^{2^{n-2}} = 1$. We therefore now have

$\omega^{2^{n-1}} + 1 = 0$.

If we add $q-1$ to both sides, we get

$\omega^{2^{n-1}} = q-1$

(since $1 + (q-1) = q = 0 \pmod q$).

Squaring both sides also gives us

$\omega^{2^n} = 1$.

(To see that $(q-1)^2 = 1$, you can either think of $(q-1)$ as acting like $-1$, or if you like you can expand it out to $q^2 - 2q + 1 = 1 \pmod q$.)

Tomorrow we’ll see how to use some of the group properties we proved earlier to deduce from these equations the order of $\omega$.

1. Aha! Here’s where we need $q$ to be prime!
| Tagged , , , , , , | 2 Comments

## MaBloWriMo 20: the group X star

So, where are we? Recall that we are assuming (in order to get a contradiction) that $M_n$ is not prime, and we picked a smallish divisor $q$ (“smallish” meaning $q^2 \leq M_n$). We then defined the set $X$ as

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

that is, combinations of $1$ and $\sqrt 3$ where the coefficients are between $0$ and $q-1$. We defined a binary operation on $X$ which works by multiplying and then reducing the coefficients $\pmod q$. This is not a group, since for example $0$ doesn’t have an inverse. But in the last post we saw that we can make a group $X^*$ simply by including only the elements from $X$ that do have inverses.

Recall that $\omega = 2 + \sqrt 3$ is in $X$ (as long as $q$ is not $2$—which it can’t be, since $M_n = 2^n - 1$ is odd), and we know that $\omega \overline{\omega} = 1$, so $\omega$ has an inverse and we conclude $\omega \in X^*$.

You might enjoy figuring out what $X^*$ looks like in the case $q = 3$. Tomorrow, we’ll start thinking about the implications of our assumption that $s_{n-2}$ is divisible by $M_n$, and in particular what it means about the order of $\omega$ in $X^*$.

## MaBloWriMo 19: groups from monoids

So, you have a monoid, that is, a set with an associative binary operation that has an identity element. But not all elements have inverses, so it is not a group. Assuming you really want a group, what can you do?

It turns out there is a very simple answer: just throw away all the elements that don’t have inverses! That is, given a monoid $M$, form the subset $M^* \subset M$ of all the elements of $M$ that do have an inverse with respect to the binary operation. I claim that $M^*$ is in fact a group (under the same binary operation). Let’s prove it. We have to check that $M^*$ satisfies all the laws of a group.

• By assumption, there is some $e \in M$ which is the identity for the binary operation. So in particular $e \odot e = e$, which means that $e$ is its own inverse; so $e \in M^*$.
• We know all the elements in $M^*$ have an inverse in $M$, but we still need to make sure those inverses actually end up in $M^*$! If $a \in M^*$ then by definition $a$ has an inverse, $a^{-1}$, which means that $a \odot a^{-1} = a^{-1} \odot a = e$. Note that these equations are completely symmetric: not only is $a^{-1}$ the inverse for $a$, we can also say that $a$ is the inverse for $a^{-1}$. So $a^{-1}$ must be in $M^*$ too.
• If the binary operation is associative for $M$ then it will definitely be assocative for $M^*$ too (since associativity holds for all elements of $M$, of which $M^*$ is a subset).
• There is one more crucial thing we have to check: it is not a priori clear that $M^*$ is even closed under the binary operation—might there be some $a, b \in M^*$ such that $a \odot b$ is in $M$ but not in $M^*$?. But in fact if $a$ and $b$ both have inverses, then $a \odot b$ must have an inverse as well, namely, $b^{-1} \odot a^{-1}$, since

$(b^{-1} \odot a^{-1}) \odot (a \odot b) = b^{-1} \odot (a^{-1} \odot a) \odot b = b^{-1} \odot b = e$.

(The fact that $(a \odot b)^{-1} = b^{-1} \odot a^{-1}$ is sometimes called the “socks-shoes property”: you put on your socks first ($a$), and then your shoes ($b$); the inverse operation is to first take off your shoes ($b^{-1}$), then your socks ($a^{-1}$).)

So if $a$ and $b$ are in $M^*$ then $a \odot b$ must be as well.

| Tagged , , , , , , | 1 Comment

## MaBloWriMo 18: X is not a group

Yesterday we defined

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

along with a binary operation which works by multiplying and reducing coefficients $\pmod q$. So, is this a group? Well, let’s check:

• It’s a bit tedious to prove formally, but the binary operation is in fact associative. Intuitively this follows from the fact that we could choose to do the reductions $\pmod q$ immediately, or delay them until after completing several multiplications—and we know that normal multiplication is indeed associative.
• $1 = 1 + 0\sqrt{3}$ is the identity for the operation.
• Do all elements in $X$ have inverses? Well… no! One simple counterexample is $0 \in X$: there cannot possibly be any element $x \in X$ such that $0x = 1$. But $0$ is not the only one. Depending on the choice of $q$, there can be many elements of $X$ without inverses. For example, when $q = 3$, you can check that $\sqrt 3$ and $2 \sqrt{3}$ do not have inverses either (though the other elements do).

So $X$ is a monoid (it has an associative binary operation with an identity) but it is not a group, because not every element has an inverse. Argh! But we really need a group, so that we have something to which we can apply all those nifty facts we proved! Well, fear not, it turns out that there is a simple way to turn any monoid into a group. Do you have an idea? Tomorrow I’ll explain how, and prove that it does in fact result in a valid group.

| Tagged , , , , , , | 1 Comment