Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
3  
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
2  
Can you do it for $n=6$? –  Phira Oct 28 '11 at 13:49

6 Answers 6

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

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

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.

share|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|improve this answer

Your Answer

 
discard

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.