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.
This entry was posted in algebra, arithmetic, group theory, number theory and tagged , , , . Bookmark the permalink.

1 Response to MaBloWriMo 18: X is not a group

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

Comments are closed.