# Multiplication groups

1. Aug 16, 2011

### gtfitzpatrick

1. The problem statement, all variables and given/known data
Let U(n) be the set of all positive integers less than n and relatively prime to n. Prove that U(n) is agroup under multiplication modulo n

2. Relevant equations

3. The attempt at a solution

n $|$ a-a' implies n$|$ b(a-a') =ab-a'b
and n$|$b-b' implies n$|$a'(b-b') =a'b-a'b'
implies n$|$ab-a'b+a'b-a'b'
=ab-a'b'
ie ab=a'b'modn

have i done enough with this?

Last edited: Aug 16, 2011
2. Aug 16, 2011

### HallsofIvy

Re: Groups

You need to state precisely what each of those is showing. In order that a set, together with an operation, be a group you must show:
1) The set is closed under the operation.
2) The operation is associative.
3) There is an identity for the operation in the set.
4) There is an inverse for every member of the set.

Exactly which of your "implications" does each of those?

3. Aug 16, 2011

### gtfitzpatrick

Re: Groups

if ac$\equiv$ab mod n
then n $|$ ac.ab =a(c-b) by Euclids Therom as gcd(n,a) = 1
so we must have n $|$ c-b
ie c$\equiv$ b mod n

4. Aug 16, 2011

### fzero

Re: Groups

For any $a\in U(n)$, $a<n$, so $n|a$ is false. If it were true, you'd find that $ab\mod n=0$.

You need to explicitly show that $ab \mod n$ is both less than $n$ and relatively prime to $n$. As a general suggestion, a good proof includes some text to explain the assumptions and logic behind the steps. You'd have caught your mistake if you actually tried to translate the properties stated into the equations you were using.

5. Aug 16, 2011

### HallsofIvy

Re: Groups

That is not at all relevant. It shows that the "cancelation" law applies to this operation but does NOT show that every member has an inverse. The set of all integers with the operation of multiplication satisfies "cancelation" but is not a group.

(This was in response to gtfitzpatrick's post. fzero got his in while I was typing.)

6. Aug 16, 2011

### gtfitzpatrick

Re: Groups

first i need to show that multiplication mod n is a binary operation on U(n)

suppose a,b $\in$ U(n) then a has multiplicative inverse $a^{-1}$ and b similarly has $b^{-1}$

now
$(b^{-1}a^{-1})(ab) = (b^{-1}(a^{-1}a)b) = (b^{-1}(1)b) = 1$
and
$(ab)(b^{-1}a^{-1}) = (a(bb^{-1})(a^{-1}) = (a(1)a^{-1}) = 1$
so $(b^{-1}a^{-1})$ is the multiplicative inverse of ab and ab is a unit. Therefore multiplication mod n is abinary op on U(n)

Next assocativity

choose a,b,c $\in$ U(n)

we want to show (ab mod n)c mod n = a(bc mod n) mod n

ab mod n = ab + mn
then (ab + mn)c mod n = (ab + mn)c + ln = abc + (mc + l)n for m,l $\in$ Z
likewise a(bc mod n) mod n = a(bc + pn) + qn = (abc + (ap+q)n for p,q $\in$ Z
but clearly abc + (mc+l)n $\equiv$ mod n abc + (qp+q)n

identity e=1 works since 1a = a1 = a for a $\in$ U(n)

next inverses

7. Aug 16, 2011

### gtfitzpatrick

Re: Groups

inverses
a $\in$ U(n) gcd (a,n) = 1 => sa+tn=1
working on mod n we see that sa $\equiv$ mod n 1. But we have thus found our inverse to a, s mod n. We should verify that gcd(s,n) = 1 to see that this inverse is actually in the group, but the equality sa+tn=1 infact inplies gcd(s,n)=1

this seems to be a very dragged out proof, is it correct?

8. Aug 16, 2011

### fzero

Re: Groups

You still haven't proven that $U(n)$ is closed under the product. This step should actually be done first, as the other group properties depend on it being true.

9. Aug 16, 2011

### gtfitzpatrick

Re: Groups

a,b $\in$ U(n) => gcd(a,n)=gcd(b,n)=1

assume gcd(ab,n) = 1
=>x(ab)+y(n)=1
gives (xa)b+(y)n=1 => gcd(b,n)=1
also (xb)a+(y)n = 1 => gcd(a,n)=1

let x be a prime integer such that x$|$ab and x$|$n
then x$|$a or x$|$b , given gcd(a,n)=gcd(b,n)=1 =>x=$\pm$1
therefore gcd (ab,n) = 1
ie ab $\in$ U(n)

10. Aug 16, 2011

### fzero

Re: Groups

This part technically doesn't contribute to closure, but is a nice consistency check.

It is obvious, but you should also remark that $ab \mod n < n$ for completeness.