modulo arithmetic proof

**WWTL@WHL** · February 17th 2008, 07:58 AM

Afternoon guys, I'm stuck on this proof and I'd really appreciate it if someone could help solve it. ( $Z$ = set of integers)

Question/Theorem

Let $Z^*_p$ be the set of nonzero integers modulo p. ( $p \geq 2$ ) Prove $Z^*_p$ is a group with multiplication mod $p$ if and only if $p$ is a prime number.

__________________________________________________ ______________

My (lame) effort so far:

We need to show:
(1) $Z^*_p$ is a group with multiplication mod $p$ $\Rightarrow$ $p$ is prime.

(2) if $p$ is prime, $Z^*_p$ is a group with multiplication mod $p$
__________________________________________________ _______________

(1) $\forall x \in Z^*_p$ , $\exists x^{-1} \in Z^*_p$ such that $xx^{-1} = 1$

so $xx^{-1} = 1 \mod p$
$xx^{-1} -1 = 0 \mod p$
$\Rightarrow$ p divides $xx^{-1} -1$
$\Rightarrow \exists a \in Z$ such that $xx^{-1} - pa =1$

I don't know where to go from here, or indeed if this is the right way of approaching this.
__________________________________________________ __________________

(2) if $p$ is prime, then any integer $q$ such that $1 \leq q \leq p-1$ is coprime to $p$ and so $\exists$ n,m $\in Z$ such that $np + mq =1$

Now using that, we need to show the properties of a group are satisfied.

Showing associativity and identity (=1) are easy enough. But I don't know how to show an inverse exists. i.e. show that $\exists x^{-1} \in Z^*_p$ such that $xx^{-1} = 1$ using the above property of a prime number.

__________________________________________________ __________________

Please help

Thank you.

**ThePerfectHacker** · February 17th 2008, 08:14 AM

Originally Posted by WWTL@WHL

Afternoon guys, I'm stuck on this proof and I'd really appreciate it if someone could help solve it. ( $Z$ = set of integers).

Consider $\{ [0],[1],...,[p-1]\}$ we want to show if $[x]\not = [0]$ then there exists $[y]$ such that $[xy]=[1]$ . This is equvalent to saying $xy\equiv 1(\bmod p)$ . Since $p$ is prime it means $\gcd(x,p)=1$ since $[x]\not = [0]$ . Thus, $ax+bp = 1$ for some integers $a,b$ . This means that $ax\equiv 1(\bmod p)$ for some $a$ . Thus, if we let $[y] = [a]$ then $[xy]=1$ .

**WWTL@WHL** · February 17th 2008, 08:31 AM

Originally Posted by ThePerfectHacker

Consider $\{ [0],[1],...,[p-1]\}$ we want to show if $[x]\not = [0]$ then there exists $[y]$ such that $[xy]=[1]$ . This is equvalent to saying $xy\equiv 1(\bmod p)$ . Since $p$ is prime it means $\gcd(x,p)=1$ since $[x]\not = [0]$ . Thus, $ax+bp = 1$ for some integers $a,b$ . This means that $ax\equiv 1(\bmod p)$ for some $a$ . Thus, if we let $[y] = [a]$ then $[xy]=1$ .

Thank you very much, perfecthacker! I totally forgot about the 'nonzero' part, so I guess I was barking up the wrong tree with that $xx^{-1} -1 = 0 (modp)$ stuff.

Now I'm going to be very, very cheeky and ask for any points for the 2nd bit of the proof. i.e. we can't assume p is prime, and deduce it is from the fact that $Z^*_p$ satisying the properties of a group.

I've outlined my thoughts in my original post, but admittedly, I don't have any concrete ideas. If you, or anyone else, can nudge me in the right direction, that'd be superb.

**ThePerfectHacker** · February 17th 2008, 08:46 AM

Suppose $n\geq 2$ (nobody ever cares for when $n=1$ because the group on only one element is really unintersing and never comes up anyway). We will show $\mathbb{Z}_n^{\text{x}}$ is not a field. If it is a field then $[a][b]\not = [0]$ if $[a],[b]\not = [0]$ (why?). But if $n$ is not a prime then we can write $n=ab$ where $1<a,b<n$ , thus $[a][b] = [n] = [0]$ while $[a],[b]\not = [0]$ . This means it cannot be a field if $n$ has factors.

**WWTL@WHL** · February 17th 2008, 09:00 AM

Originally Posted by ThePerfectHacker

If it is a field then $[a][b]\not = [0]$ if $[a],[b]\not = [0]$ (why?).

Thanks for the reply, but I'm confused. Consider $Z^*_6$ .

Let $[a] = [2] \not = [0]$ and let $[b] = [3] \not = [0]$

Then surely $[ab] = [a][b] = (2mod6) . (3mod6) = 6mod6 = [0]$ ?

**ThePerfectHacker** · February 17th 2008, 12:08 PM

Originally Posted by WWTL@WHL

Thanks for the reply, but I'm confused. Consider $Z^*_6$ .

Let $[a] = [2] \not = [0]$ and let $[b] = [3] \not = [0]$

Then surely $[ab] = [a][b] = (2mod6) . (3mod6) = 6mod6 = [0]$ ?

Yes [a]=[2] and [b]=[3] are non-zero and [2][3] = [6] = [0] so it means it cannot be a group under multiplication.

**WWTL@WHL** · February 17th 2008, 12:33 PM

Originally Posted by ThePerfectHacker

Yes [a]=[2] and [b]=[3] are non-zero and [2][3] = [6] = [0] so it means it cannot be a group under multiplication.

D'oh.

Of course, yes.

Thank you very much for all your help.

Thread: modulo arithmetic proof

LinkBack

Thread Tools

Display

modulo arithmetic proof

Similar Math Help Forum Discussions

modulo arithmetic proof

modulo arithmetic

Modulo Arithmetic

modulo arithmetic

Modulo arithmetic

Search Tags