# Prove that: set $\{1, 2, 3, …, n - 1\}$ is group under multiplication modulo $n$?

Prove that: The set $\{1, 2, 3, ..., n - 1\}$ is group under multiplication modulo $n$ if and only if $n$ is a prime number.

(Do not use Euler phi function)

-
This looks like homework. Is it? What do you know about the invertibility of the elements if $n$ isn't prime? –  Tyler Oct 28 '11 at 13:39
Is this homework? If so, please tag it as such. What have you tried? Is your problem with the "if" or the "only if" direction? –  Henning Makholm Oct 28 '11 at 13:40
No, I try to self study :D Not homework :D. I have proven that by Euler phi function. Have another solution ?? –  qwerty89 Oct 28 '11 at 13:41
You still need to answer those other questions, though. –  Henning Makholm Oct 28 '11 at 13:48
Can you do it for $n=6$? –  Phira Oct 28 '11 at 13:49
show 1 more comment

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?

-

Note that if $ab\equiv 1 \pmod{n}$, then $\gcd(n,a)=\gcd(n,b)=1$. So what elements could possibly have multiplicative inverses?

-

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$ is equivalent to $0$ 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$ is equivalent to $1$ $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.

-

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.

-

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

-
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.)
The other direction---that if $n$ is not prime then this thing is not a group, is easier.