Is U(n) a Group Under Multiplication Modulo n?

[cragar]

Homework Statement

Show that the set U(n) = {x < n : gcd(x, n) = 1} under multiplication modulo n is a group.

Homework Equations

3. The Attempt at a Solution [/B]
I know that it is important to have the gcd=1 other wise you would eventually have an element that under the group operation would be a multiple of n which would have a remainder of 0 and could generate nothing new after that under multiplication.

xr+bn=gcd(x,n)=1 .

 

[ChrisVer]

how do you show that a set of elements is/forms a group?

 

[cragar]

To make sure that inverse exist we need to have 2 group elements a,b such that ab=cn+1 , gcd(a,n)=1 and gcd(b,n)=1 and c is a multiple of n.
so ab-cn=1. I am trying to figure out a way to prove that 2 element multiplied together will get me one more than a multiple on n.

 

[Dick]

To make sure that inverse exist we need to have 2 group elements a,b such that ab=cn+1 , gcd(a,n)=1 and gcd(b,n)=1 and c is a multiple of n.
so ab-cn=1. I am trying to figure out a way to prove that 2 element multiplied together will get me one more than a multiple on n.

If a and b are relatively prime then there exist integers k and l such that ak+bl=1. Use that.

 

[cragar]

if ab-cn=1 then gcd(ab,cn)=1 because these are consecutive natural numbers. if they shared common factors then it should divide their difference but their difference is 1.
let a be a natural number such that gcd(a,n)=1 and a<n, now we need to look for a natural number b such that ab-cn=1, by the euclidean algorithm integers should exist.
we know that gcd(b,cn)=1 otherwise if they shared a common factor this could be factored out and then we would have a product of 2 integers equallying one. but we just factored out their common factor that is larger than 1 so this is a contradiction. for the moment I am going to look at the case where ab-n=1.
ab=n+1, let a and b <n, claim b< n, assume for contradiction that b>n-1, if b were at least n and a was >2 then ba=2n which is larger than n+1, so this is a contradiction therefore b<n, so such a b exists, there exists a,b such that ab=n+1,

 

[Dick]

if ab-cn=1 then gcd(ab,cn)=1 because these are consecutive natural numbers. if they shared common factors then it should divide their difference but their difference is 1.
let a be a natural number such that gcd(a,n)=1 and a<n, now we need to look for a natural number b such that ab-cn=1, by the euclidean algorithm integers should exist.
we know that gcd(b,cn)=1 otherwise if they shared a common factor this could be factored out and then we would have a product of 2 integers equallying one. but we just factored out their common factor that is larger than 1 so this is a contradiction. for the moment I am going to look at the case where ab-n=1.
ab=n+1, let a and b <n, claim b< n, assume for contradiction that b>n-1, if b were at least n and a was >2 then ba=2n which is larger than n+1, so this is a contradiction therefore b<n, so such a b exists, there exists a,b such that ab=n+1,

If you know there are integers b and c such that ab-cn=1, then you have pretty much shown that a has an inverse, haven't you? I don't know what you are trying to say with the rest of that argument.

 

[ChrisVer]

take the concrete example of U(8) = \{ 1, 3,5, 7 \}..
what do you get by trying some of the multiplications?