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.
 A: 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.
A: $\Rightarrow$ is simple and proven multiple times above.
$\Leftarrow$: There is no need to rely on the Euclidian algorithm:
Let $1 \leq j \leq p-1$. Then by the pigeon principle, among the numbers $j, j^2, j^3,..., j^{p+1}$ there are two congruent modulo $p$.
Thus 
$$j^k \cong j^l \mod p \, ;\, k< l \,.$$
This means $p| j^k(j^{l-k}-1)$. Since $p$ and $j$ are relatiovely prime it follows that
$$j^{l-k} \cong 1 \mod p \, ;\, l-k \geq 1 \,.$$
From here proving that this is a group is simple...
P.S.
Alternately you can also use the following argument:
For all $1 \leq j \leq p-1$, the function $f: \{ 1,2,3,.., p-1 \} \rightarrow  \{ 1,2,3,.., p-1 \}$, is well defined (prove it) and injective (prove it). Thus it has to be surjective.
A: 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?
A: Note that if $ab\equiv 1 \pmod{n}$, then $\gcd(n,a)=\gcd(n,b)=1$. So what elements could possibly have multiplicative inverses?
A: HINT $\rm\quad a^{-1}\:$ exists $\rm\: mod\ n\ \iff\ \exists\ b,c\!\!:\ a\:b + c\:n = 1\ \iff\  \gcd(a,n) = 1$
So all naturals $\rm < n\:$ are invertible $\rm\:mod\ n\:$ iff $\rm\:n\:$ is coprime to all smaller naturals iff $\rm\:n\:$ is prime.
A: I wrote this answer to what is nearly the same question.  If $n$ is prime and $x$ is not a multiple of $n$ (so in mod-$n$, $x$ is not $0$), how do you find the multiplicative inverse of $x$? (Other aspects of proving the thing is a group are easy.)
(A harder problem is proving that that multiplicative group is a cyclic group.)
The other direction---that if $n$ is not prime then this thing is not a group, is easier.
