# Prove that that $U(n)$ is an abelian group.

Prove that that $U(n)$, which is the set of all numbers relatively prime to $n$ that are greater than or equal to one or less than or equal to $n-1$ is an Abelian group.

My thought process: for $a, b \in U(n)$

Associativity: $(a + b) + c = a + (b + c)$
Identity: $1$ is in the set so $a\cdot 1 = a = 1\cdot a$
Inverse: I'm stuck on how to determine the inverse of the set if it exist.
Abelian criteria : $a\cdot b = b\cdot a$

Thanks

-
Abelian group...wrt multiplication modulo $\,n\,$ ...That sum has nothing to do with this here. –  DonAntonio Jan 13 '13 at 0:58
FYI, $U(n)$ is sometimes used to denote the $n^{th}$ unitary group (en.wikipedia.org/wiki/Unitary_group), which is noncommutative for $n > 1$. A less ambiguous notation for the group you want to describe is $(\mathbb{Z}/n\mathbb{Z})^{\times}$. –  Qiaochu Yuan Jan 13 '13 at 1:16

It’s true that you know that multiplication in $\Bbb Z$ is associative and commutative, but you still have to prove that multiplication in $U(n)$ is associative and commutative, i.e., that multiplication modulo $n$ is associative and commutative. To show that every element of $U(n)$ has a multiplicative inverse in $U(n)$, use Bézout’s lemma: if $a$ and $n$ are relatively prime, there are integers $u$ and $v$ such that $au+vn=1$.

-

Let $k\in U(n)$, thus $gcd(k,n)=1$ and so there exist integers $x,y$ such that $xk+yn=1$. Taken modulo $n$ this equation becomes $xk=1$ and so, modulo $n$, the inverse of $k$ is $x$.

Also, note that the group operation is multiplication and not addition. Proving the other abelian group axioms is easy.

-

The associative law and the fact that $U(n)$ is abelian follows from those properties in the commutative ring $\mathbb Z_n$. Since 1 is trivially relatively prime to $n$, $U(n)$ has an identity element. We proceed to show the existence of inverses:

Let $a$ be relatively prime to $n$ and define the map $f:U(n)\to U(n)$ by $f(x)=ax$; the function actually maps into $U(n)$, since if $(x,n)=1$, then $(ax,n)=(a,n)(x,n)=1$.

I claim $f$ is injective. For, $f(x)=f(y)$ implies $ax\equiv ay$ and so $a(x-y)\equiv 0\pmod n$. Therefore, $x\equiv y$, since $n$ shares no factors with $a$. Thus, $f$ is injective as desired. The finite domain of $f$ is the same as its codomain, so $f$ also is surjective, mapping some $x_0$ to $1$. I.e. $f(x_0)=ax_0=1$.

-
Note that the definition of the group in the question was in terms of just numbers (between 1 and $n-1$), not congruence classes. The penalty for adopting this definition is that the group operation is not just multiplication but multiplication followed by reduction modulo $n$. So nice proofs like yours have to be mixed with a lot of reductions. For instance, "the function actually maps into $U(n)$" is not literally true. The reductions are not a serious problem for people who know the subject, but they can be an obstacle for those who are just learning it. –  Andreas Blass Jan 13 '13 at 2:05
@AndreasBlass It is a good point. I now recall when I first learned this that I would always have to recite to myself, "$[ab]_n=[a]_n[b]_n$, right?" and similar questions, which ultimately get in the way of the purpose (as I see it) of abstracting these things as groups. –  peoplepower Jan 13 '13 at 2:11