I came across the problem
Prove that the set of all positive integers less than $n$ and relatively prime to n form a group under multiplication modulo n.
Proving the associativity of multiplication modulo n, closure and existence of identity are fairly easy.
But how would we prove that there is inverse for all elements i.e.$\forall$ $a \in U(n),\space \exists b \in U(n)$ such that $ab(modn) = 1$?
MY TRY:
I know that if $gcd(a,n) = 1$ $\exists x$ such that $ax(modn) = 1$. But $x$ should be in U(n) in order to complete the proof.
Also, from the theory of diophantine equations such $x$ is not unique rather if $x_{0}$ is a particular solution then, $x_{0}+nt$ for $t\in \Bbb Z$ is also a solution.
So, we can find some x such that $0\le x \le n-1$ and $ax(modn) = 1$. But, how would we prove that such $x$ is relative prime to n i.e. $gcd(x,n) = 1$?
I got stuck here. Any hint in that direction would be a great help Other ways of solving the problem are also welcomed.
Best Answer
Hint:
You have shown for each $a$ coprime to $n$ there is an $x$ so that $ax=1$ mod $n$.
Towards a contradiction, assume $\gcd(x,n) = d \neq 1$. Then any linear combination $rx+sn$ must be divisible by $d$... What happens if we take $r=a$? Do you see how to finish the proof from here?
I hope this helps ^_^