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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →