Results 1 to 7 of 7

Math Help - modulo arithmetic proof

  1. #1
    Member
    Joined
    Sep 2007
    Posts
    127

    modulo arithmetic proof

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by WWTL@WHL View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2007
    Posts
    127
    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2007
    Posts
    127
    Quote Originally Posted by ThePerfectHacker View Post
    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] ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by WWTL@WHL View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2007
    Posts
    127
    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modulo arithmetic proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 31st 2011, 08:27 AM
  2. modulo arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 15th 2010, 07:10 AM
  3. Modulo Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 9th 2009, 03:56 AM
  4. modulo arithmetic
    Posted in the Math Topics Forum
    Replies: 7
    Last Post: December 31st 2007, 09:52 AM
  5. Modulo arithmetic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 2nd 2007, 05:16 AM

Search Tags


/mathhelpforum @mathhelpforum