Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Abelian group...wrt multiplication modulo $\,n\,$ ...That sum has nothing to do with this here. –  DonAntonio Jan 13 '13 at 0:58
1  
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

3 Answers 3

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$.

share|improve this answer

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.

share|improve this answer

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.