Results 1 to 3 of 3

Math Help - help with defining a relation ~ on Z_p

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    MD
    Posts
    14

    help with defining a relation ~ on Z_p

    The question is as follows:

    Define a relation ~ on Zp where p is an odd prime, as follows: [a]p ~ [b]p if 2ia = b mod p for some i in N. show that ~ is an equivalence relation on Zp

    I know that to show an equivalence relation you have to show the reflexive, symmetric and transitive properties hold.

    reflexive: [a]p ~ [a]p 2ia = a mod p this is true since any multiple of a consequence class is equal to itself

    symmetric: [a]p ~ [b]p , [b]p ~ [a]p I know that I need to show that 2ia = b mod p and 2ib = a mod p but I am unsure if the logic is sound.
    2ia = b mod p then 2ia = pq + b for some integer q
    2ia - b = pq so p|(2ia - b) however p is an odd prime so it can not divide 2i so p|(a - b) and p|(b - a) then p|(2ib - a)
    then 2ib - a = pq so 2ib = a mod p

    Transitive: [a]p ~ [b]p [b]p ~ [c]p [a]p ~ [c]p 2ia = b mod p and 2ib = c mod p then 2ia = c mod p
    2ia = pq + b and 2ib = pr + c for integers q, r
    then 2ia + 2ib = pq + pr + c+ b
    2i(a + b) - (c + b) = p(q + r)
    so p divides the LHS but as in the above argument p does not divide 2i so p|[(a + b) - (c + b)]
    so p|(a - c) then p|(2ia - c) so 2ia - c = p(q + r) so 2ia = c mod p

    have I done enough to prove the relation and is my arguments logically sound?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: help with defining a relation ~ on Z_p

    Quote Originally Posted by bskcase98 View Post
    ...
    reflexive: [a]p ~ [a]p 2ia = a mod p this is true since any multiple of a consequence class is equal to itself
    What you should observe here is that 2^0a = a \mod p. That's what shows that a ~ a.

    Quote Originally Posted by bskcase98 View Post
    symmetric:
    ...
    2ia - b = pq so p|(2ia - b) however p is an odd prime so it can not divide 2i so p|(a - b)
    That actually doesn't follow.

    What you need to do is show that starting with 2^ia = b \mod p,

    you can show that there's some j such that 2^jb = a \mod p. What could j be?

    Working backwards, if both those hold, then: 2^ia = b \mod p, and 2^jb = a \mod p,

    so 2^{i+j}a = 2^jb = a\mod p, so 2^{i+j}aa^{-1} = aa^{-1} = 1 \mod p, so 2^{i+j} = 1\mod p.

    So find n such that 2^n = 1\mod p, and then 2^ia = b \mod p will imply 2^{n-i}b = a \mod p.

    -----------------------

    For the transitive: Those aren't "the same i".

    From a~b and b~c you should conclude that:

    \text{"For some } i \in \mathbb{N}, \ 2^ia = b \mod p, \text{ and, for some } j \in \mathbb{N}, \ 2^jb = c \mod p \text{ ."}

    After that consider 2^{i+j}a = ? \mod p.
    Last edited by johnsomeone; October 16th 2012 at 09:00 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    MD
    Posts
    14

    Re: help with defining a relation ~ on Z_p

    thank you very much for the help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 7th 2011, 12:46 AM
  2. defining an operator - 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 4th 2009, 11:31 AM
  3. Defining an operaor
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 28th 2009, 12:21 PM
  4. Defining a plane
    Posted in the Calculus Forum
    Replies: 3
    Last Post: September 15th 2009, 04:15 AM
  5. Defining the p.m.f. of X
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: February 15th 2009, 09:01 PM

Search Tags


/mathhelpforum @mathhelpforum