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.

EDIT: It looks like the question may have been changed. I seem to remember it asking why, in the set $ \{ 1, 2, 3, ... n-1 \} $ equipped with multiplication modulo $n$, inverses exist if and only if $n$ is a prime number. Either way, the following only answers why inverses exist (this does most of the work in showing it's a group, anyway):
Both directions follow from Bézout's Lemma (which in turn follows from Euclid's Algorithm): Let $a, b, c $ be natural numbers. Then there exist integers $u ,v $ such that $ au + bv = c $ if and only if $ \mbox{hcf}(a,b) | c $. 
This easily proves your 'if' direction: if $n$ is prime, then $\mbox{hcf}(k,n) = 1 $ for all $k$ in $ \{ 1,2,3, ... n-1 \}$. So there exists integers $u, v$ such that $ ku + nv = 1 $, i.e. $ ku = 1 \ (\mbox{mod } n)$ 
To prove the 'only if' direction, note that each $k$ in $ \{1, 2, 3, ... n-1\} $ having a multiplicative inverse implies the existence of integers $u,v$ such that $ ku + nv = 1 $. So $\mbox{hcf}(k,n) | 1 $ for all $k$, i.e. $ \mbox{hcf}(k,n) = 1 $ for all $k$. Can you see why this means $n$ is prime?
