# Thread: help with defining a relation ~ on Z_p

1. ## 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?

2. ## Re: help with defining a relation ~ on Z_p

Originally Posted by bskcase98
...
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 $\displaystyle 2^0a = a \mod p$. That's what shows that a ~ a.

Originally Posted by bskcase98
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 $\displaystyle 2^ia = b \mod p$,

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

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

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

So find n such that $\displaystyle 2^n = 1\mod p,$ and then $\displaystyle 2^ia = b \mod p$ will imply $\displaystyle 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:

$\displaystyle \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 $\displaystyle 2^{i+j}a = ? \mod p$.

3. ## Re: help with defining a relation ~ on Z_p

thank you very much for the help