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
    You dont have to do anything to prove that $S^\times$ is a group. A group is by definition a monoid such that every element has an inverse. Since you are "tossing out" everything that does not have an inverse, you are done by contruction. I dont know what you mean by $U_n$.2012-07-06
  • 1
    Show that $S^\times$ is closed under the operation and contains the identity element ... as the operation is associative and elements of $S^\times$ have inverses, you have a group. What is $U_n$?2012-07-06
  • 0
    **Hint**: can you write $(ab)^{-1}$ in terms of $a^{-1}$ and $b^{-1}$?2012-07-06
  • 0
    You should show where you are stuck and what you have tried or at the very least demonstrate that you understand the terms involved in the question (that you know what a group is, for example)2012-07-06
  • 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.