Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
Can you do it for $n=6$? – Phira Oct 28 '11 at 13:49

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?

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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


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


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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.