For n>1 consider the set,

G_n={gcd(x,n)=1|1<=x<=n}

It can be shown from group theory this is a group under multiplication mudolo n.

**Proof**:

*Closure*: We have gcd(a,n)=1 and gcd(b,n)=1 then gcd(ab,n)=1.

*Associativity*Trivial. Since G_n is a proper algebraic binary structuce of Z_n.

*Identity*Trivial, 1 is in G_n.

*Existence of inverse*.

Let,

a_1,a_2,...,a_k

Be all the elements in G_n

Let a be in G_n

Form the numbers,

aa_1,aa_2,...,aa_k

Note if,

aa_i=aa_j (mod n)

Then since gcd(a,n)=1 we have,

a_i=a_j

But that is not possible for 1<=a_i,a_j<=n

Thus, all,

aa_1,aa_2,...,aa_k

Are distinct.

By

Dirichlet's Pigeonhole Principle
It consits of,

a_1,a_2,...a_k

In which one is 1 (identity)

Q.E.D.

Now the equation,

ax=1(mod n)

For gcd(a,n)=1

Is asking to solve this linear equation in the group G_n

Which we know always have a

**unique** solution.