Hw4 Problem 1

Return to Homework 4, Homework Problems, Glossary, Theorems

Problem 1

(a) Show that multiplication is a well-defined binary operation on the set $\mathbb{Z_n}$ of congruence classes of integers modulo $n$.

(b) Given an integer $n \ge 1$, let $\mathbb{Z^{*}_{n}}$ be the set of elements $\bar x \in \mathbb{Z_{n}}$ such that there exists $\bar y \in \mathbb{Z_{n}}$ with $\bar x \bar y = \bar 1$. Show that $\mathbb{Z^{*}_{n}}$ with the operation of multiplication is a group.

(c) Write multiplication tables for $\mathbb Z^*_8$,$\mathbb Z^*_{10}$ and $\mathbb Z^*_{12}$.

(d) Show that $\mathbb{Z^{*}_{8}} \simeq \mathbb{Z^{*}_{12}}$, but that $\mathbb{Z^{*}_{10}}$ is not isomorphic to $\mathbb{Z^{*}_{8}}$ and $\mathbb{Z^{*}_{12}}$.

---

Solutions

(a)

For each $(a,b)\in \mathbb{Z_n}\times \mathbb{Z_n}$, when $a\times b\ge n$, $a*b=a\times b-n\in\mathbb{Z_n}$. When $a\times b<n$,$a*b=a\times b\in\mathbb{Z_n}$. So multiplication is a well-defined binary operation on the set $\mathbb{Z_n}$.

This just gives the definition of the operation; it doesn't show it's well-defined.

(b)

$\mathscr{G_{1}}$: Let $\bar x, \ \bar y, \ \bar z \in \mathbb{Z_{n}}$.

Now,

(1)

\begin{align} ( \bar x \bar y) \bar z = \overline{(xy)z}=\overline{x(yz)} = \bar x (\bar y \bar z) \end{align}

where the middle equality holds since multiplication is associative in $\mathbb{Z}$.

Hence, multiplication is associative in $\mathbb{Z}_n^*$.

$\mathscr{G_{2}}$: Note $1 \cdot 1 = 1$, so $1 \in \mathbb{Z}_n^*$. Let $x \in \mathbb{Z_{n}}$. Now, $x \cdot 1 = 1 \cdot x = x$. Thus, $1$ is the identity element.

$\mathscr{G_{3}}$: By definition, an element is in $\mathbb{Z}_n^*$ only if it has a multiplicative inverse in $\mathbb{Z}_n^*$.

Therefore the set of elements $\bar x \in \mathbb{Z_{n}}$ such that $\bar x \bar y = \bar 1$ and $\bar y \in \mathbb{Z_{n}}$, is a group.

(c)

$\mathbb Z^*_8$：

·	1	3	5	7
1	1	3	5	7
3	3	1	7	5
5	5	7	1	3
7	7	5	3	1

$\mathbb Z^*_{10}$：

·	1	3	7	9
1	1	3	7	9
3	3	9	1	7
7	7	1	9	3
9	9	7	3	1

$\mathbb Z^*_{12}$:

·	1	5	7	11
1	1	5	7	11
5	5	1	11	7
7	7	11	1	5
11	11	7	5	1

(d)

$\mathbb{Z^{*}_{8}} \simeq \mathbb{Z^{*}_{12}}$

In $\mathbb{Z^{*}_{8}}$ and $\mathbb{Z^{*}_{12}}$, each element is its own inverse, but in $\mathbb{Z^{*}_{10}}$ this is not true. Therefore $\mathbb{Z^{*}_{10}}$ is not isomorphic to $\mathbb{Z^{*}_{8}}$ and $\mathbb{Z^{*}_{12}}$.