Prove that: set $\{1, 2, 3, ..., n - 1\}$ is group under multiplication modulo $n$? Prove that: 
The set $\{1, 2, 3, ..., n - 1\}$ is a group under multiplication modulo $n$ if and only if $n$ is a prime number without using Euler's phi function.

Assume that $H=\{1,2,3,...n-1\}$ is a group. Suppose that $n$ is not a prime.
Then $n$ is composite, i.e $n=pq$ for $1<p,q<n-1$ . This implies that $pq \equiv0(mod n)$ but $0$ is not in H. Contradiction, hence $n$ must be prime.
Conversely, Suppose $n$ is a prime then  $gcd(a,n)=1$ for every a in H. Therefore, $ax=1-ny$, $x,y \in H$. So, $ax\equiv1(modn)$. That is every element of H has an inverse. This conclude that H must be a group since the identity is in H and H is associative.
