Proving U(n) is a Multiplication Group Modulo n: Homework Solution

[gtfitzpatrick]

Homework Statement

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

Homework Equations

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?

 

[HallsofIvy]

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?

 

[gtfitzpatrick]

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

 

[fzero]

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.

 

[HallsofIvy]

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

 

[gtfitzpatrick]

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

 

[gtfitzpatrick]

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?

 

[fzero]

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.

 

[gtfitzpatrick]

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)

 

[fzero]

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

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

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)

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