For n>1 consider the set,
It can be shown from group theory this is a group under multiplication mudolo n.
Closure: We have gcd(a,n)=1 and gcd(b,n)=1 then gcd(ab,n)=1.
AssociativityTrivial. Since G_n is a proper algebraic binary structuce of Z_n.
IdentityTrivial, 1 is in G_n.
Existence of inverse.
Be all the elements in G_n
Let a be in G_n
Form the numbers,
aa_i=aa_j (mod n)
Then since gcd(a,n)=1 we have,
But that is not possible for 1<=a_i,a_j<=n
By Dirichlet's Pigeonhole Principle
It consits of,
In which one is 1 (identity)
Now the equation,
Is asking to solve this linear equation in the group G_n
Which we know always have a unique solution.