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.

$\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.
