0
$\begingroup$

Say that $S$ is a monoid. Define a subset of $S$ by $S^\times := \{a\in S\mid a \text{ has an inverse}\}$

How can we show that $S^\times$ is a group with the same operation? Can we use this to prove that $U_n$ is a group?

$U_n:= \{a\in \mathbb{Z}_n\mid \gcd(a,n)=1\}$

  • 0
    Yes, but that is using$a$more general result to prove one specific instance. What you need to do is show that $U_n$ is closed under multiplication, first. One technical quibble: the "$a$" in $\Bbb{Z}_n$, and in "$\text{gcd}(a,n) = 1$" are not the same kind of thing: one is a congruence class, and another is an integer. You should also *prove* that $[a] \in \Bbb{Z}_n$ is invertible if and only if $\text{gcd}(a,n) = 1$.2012-07-06

1 Answers 1

1

The fact that $S$ is a monoid tells you that the operation is associative. You need to show that:

  1. If $a,b$ have inverses, then $ab$ has an inverse. (Just produce the inverse using the inverses of $a$ and $b$). This shows you have a set and a binary associative operation on th eset.

  2. Show that the operation has an identity; namely, the identity of $S$ lies in $S^{\times}$. (Show it has an inverse).

  3. Show that if $a\in S^{\times}$, then there exists $b\in S^{\times}$ such that $ab=1$ (just produce it; you know $b$ exists in $S$ by definition of $S^{\times}$, prove it actually lies in $S^{\times}$.

This will show $S^{\times}$ is a group.

To prove that $U_n$ is a group using this, consider the monois $\mathbb{Z}_n$. Show that $a\in\mathbb{Z}_n$ has a multiplicative inverse if and only if $\gcd(a,n)=1$.

In one direction: if there exists $b$ such that $ab\equiv 1\pmod{n}$, then there exists $k$ such that $ab-1 = kn$, hence $ab-nk = 1$, so $\gcd(a,n)$ divides $ab-nk=1$. Thus, $\gcd(a,n)=1$. Try proving the other direction yourself.