# Determine invertible and inverses in $(\mathbb Z_8, \ast)$

Let $\ast$ be defined in $\mathbb Z_8$ as follows: \begin{aligned} a \ast b = a +b+2ab\end{aligned}

Determine all the invertible elements in $(\mathbb Z_8, \ast)$ and determine, if possibile, the inverse of the class $[4]$ in $(\mathbb Z_8, \ast)$.

### Identity element

We shall say that $(\mathbb Z_8, \ast)$ has an identity element if: \begin{aligned} (\forall a \in \mathbb Z_8) \text { } (\exists \varepsilon \in \mathbb Z_8 : a \ast \varepsilon = \varepsilon \ast a = a)\end{aligned}

\begin{aligned} a+\varepsilon+2a\varepsilon = a \Rightarrow \varepsilon +2a\varepsilon = 0 \Rightarrow \varepsilon(1+2a) = 0 \Rightarrow \varepsilon = 0 \end{aligned} As $\ast$ is commutative, similarly we can prove for $\varepsilon \ast a$.

\begin{aligned} a \ast 0 = a+0+2a0 = a \end{aligned} \begin{aligned} 0\ast a = 0+a+20a = a\end{aligned}

### Invertible elements and $[4]$ inverse

We shall state that in $(\mathbb Z_8, \ast)$ there is the inverse element relative to a fixed $a$ if and only if exists $\alpha \in (\mathbb Z_8, \ast)$ so that:

\begin{aligned} a\ast \alpha = \alpha \ast a = \varepsilon \end{aligned} \begin{aligned} a+\alpha +2a\alpha = 0 \end{aligned} \begin{aligned} \alpha(2a+1) \equiv_8 -a \Rightarrow \alpha \equiv_8 -\frac{a}{(2a+1)} \end{aligned}

In particular looking at $[4]$ class, it follows: \begin{aligned} \alpha \equiv_8 -\frac{4}{(2\cdot 4+1)}=-\frac{4}{9} \end{aligned}

therefore: \begin{aligned} 9x \equiv_8 -4 \Leftrightarrow 1x \equiv_8 4 \Rightarrow x=4 \end{aligned}

which seems to be the right value as \begin{aligned} 4 \ast \alpha = 4 \ast 4 = 4+4+2\cdot 4\cdot 4 = 8 + 8\cdot 4 = 0+0\cdot 4 = 0 \end{aligned}

Does everything hold? Have I done anything wrong, anything I failed to prove?

-
The third line under Identity element should be $a+\varepsilon+2a\varepsilon=a$. I would have edited it for you, but the edit, while important, was deemed too short to be accepted. –  Rick Decker Jul 26 '12 at 15:32
@RickDecker oops... you're right, a typo while copying. Corrected, though. Thank you. –  haunted85 Jul 26 '12 at 15:38
Your definition of "identity" is wrong. –  Arturo Magidin Jul 26 '12 at 18:34

Let me mention that your definition of identity is wrong. You write:

We shall say that $(\mathbb{Z}_8,\ast)$ has an identity if $$(\forall a \in \mathbb Z_8) \text { } (\exists \varepsilon \in \mathbb Z_8 : a \ast \varepsilon = \varepsilon \ast a = a)$$

Under this formulation, the element $\varepsilon$ is allowed to change depending on $a$. This is not the usual meaning of "identity"! The identity is usually required to be the same for every element.

For example, consider the operation $\odot$ on $\mathbb{Z}$ given by $$a\odot b = 2a-b.$$ Then this operation satisfies the definition you give: given an integer $a$, let $\varepsilon=a$. Then $a\odot \varepsilon = 2a-a = a$, and $\varepsilon\odot a = 2a-a = a$. However, there is no element $\varepsilon$ that "works" for every integer: for instance, if $1\odot\varepsilon = 1$ then this means that $2-\varepsilon = 1$, so $\varepsilon = 1$. But then $2\odot\varepsilon\neq 2$.

The order of the quantifiers matters! By putting the existential quantifier after the universal quantifier, you allow the value of $\varepsilon$ to depend on the value of $a$. The correct formula for the existence of an identity is: $$\exists\varepsilon\in\mathbb{Z}_8(\forall a\in \mathbb{Z}_8\colon a\ast \varepsilon = \varepsilon\ast a = a).$$

Of course, if there is a $\varepsilon$ that works independent of $a$, then then there is one that works if we allow it to depend on $a$. In other words, $\exists a(\forall b P(a,b))$ always implies $\forall a(\exists b P(a,b))$. The converse does not hold, however, as the example above shows. (Or, for another example: it is true that for every person $a$ there is a person $b$ such that $b$ is the mother of $a$; i.e., everyone has someone who is their mother. It is not true, however, that there is a person $b$ such that for every person $a$, $b$ is the mother of $a$; i.e., there isn't someone who is everyone's mother).

There is also, in my opinion, a gap in the argument for inverses. You are correct that $\varepsilon = 0$ is an identity; and also that if $a$ has an inverse, then $$a+\alpha + 2a\alpha \equiv 0 \pmod{8}.$$ Hence, $\alpha(1+2a)\equiv -a\pmod{8}$ holds.

Now, you need to justify that you can "divide by $1+2a$". That is, that $1+2a$ has a multiplicative inverse modulo $8$. This can be done by noting that $1+2a$ is necessarily odd, and hence relatively prime to $8$. Thus, it can be solved in all cases, so every element has a $\ast$-inverse.

I will note, also, that you should have "$a\in\mathbb{Z}_8$" and not "$a\in(\mathbb{Z}_8,\ast)$". You want an element of the underlying set of your algebraic object, rather than an element of the ordered pair.

-

All looks correct, but in a couple cases you should explicitly mention why $\rm\:1+2a\:$ is cancellable or invertible mod $8$ (being odd it is coprime to $2$ so coprime to $8$ hence $\ldots$). In fact, it is idempotent $\rm\: (1\!+\!2a)^2 = 1 + 4a(a\!+\!1)\equiv 1\pmod 8,\:$ by $\rm\:2\:|\:a(a+1),\:$ so $\rm\:1/(1\!+\!2a) = 1\!+\!2a,\:$ which enables you to give a simpler formula for inverses in your group.

$\rm\ odd^2\equiv 1\pmod 8\:$ is frequently useful in elementary number theory, so it's worth remembering.

-

Determine all the invertible elements in $(\mathbb Z_8, \ast)$
You have shown that the inverse of $a$ is $\alpha \equiv_8 -\frac{a}{(2a+1)}$. I would go a step further and list out each element which has an inverse since you only have eight elements to check.
isn't enough showing $\alpha \equiv_8 -\frac{a}{(1+2a}$ to answer that part of the question? –  haunted85 Jul 26 '12 at 15:00
thank you for your advice, I'm wondering what if I ever have to deal with $\mathbb Z_n$ with very large $n$, would it be ok to just leave the general answer? Would there be further steps that I better do in order to support my proof? –  haunted85 Jul 26 '12 at 15:09
@haunted85 I think if $n$ were large, then a general answer such as what you gave here would likely be sufficient, unless it suggests some simple pattern, such as all odd integers less than $n$. –  Code-Guru Jul 26 '12 at 15:13