- #1

- 221

- 57

- Homework Statement
- If U(n) denotes the set of all positive integers less than n which are coprime with n. Then prove that U(n) is a group under multiplication modulo n.

- Relevant Equations
- I don't know..

**Closure**

Let a,b ∈U(n).

a has no common factor with n (other than 1)

b has no common factor with n(,,)

So,

If ab < n, then ab doesn't have any common factors with n.

If ab>n, then for some p,ab-pn < n.

Since ab doesn't have any common factor with n, ab-pn can't either.

(ab≠ n, because neither a nor b can have any common factors with n)

So, ab ∈ U(n)

Closure is verified.

**Associativity:**

Multiplication modulo n is associative( I'm not even going to think about proving that)

**Identity:**1 is the identity.

**Inverse:**

This is where I got obliterated...

Let a ∈ U(n).

We need an x such that:

Consider ax= pn+1 for some p.

I need to prove that

1)x= (pn+1)/a is an integer

2)It also doesn't have anything common with n.

I have zero idea how do I prove something like this... Please give me some direction.