help with defining a relation ~ on Z_p

The question is as follows:

Define a relation ~ on **Z**_{p} where p is an odd prime, as follows: [a]_{p} ~ [b]_{p} if 2^{i}a __=__ b mod p for some i in **N**. show that ~ is an equivalence relation on **Z**_{p}

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

reflexive: [a]_{p} ~ [a]_{p} 2^{i}a __=__ 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 2^{i}a __=__ b mod p and 2^{i}b __=__ a mod p but I am unsure if the logic is sound.

2^{i}a __=__ b mod p then 2^{i}a = pq + b for some integer q

2^{i}a - b = pq so p|(2^{i}a - b) however p is an odd prime so it can not divide 2^{i} so p|(a - b) and p|(b - a) then p|(2^{i}b - a)

then 2^{i}b - a = pq so 2^{i}b __=__ a mod p

Transitive: [a]_{p} ~ [b]_{p} [b]_{p} ~ [c]_{p} [a]_{p} ~ [c]_{p} 2^{i}a __=__ b mod p and 2^{i}b __=__ c mod p then 2^{i}a __=__ c mod p

2^{i}a = pq + b and 2^{i}b = pr + c for integers q, r

then 2^{i}a + 2^{i}b = pq + pr + c+ b

2^{i}(a + b) - (c + b) = p(q + r)

so p divides the LHS but as in the above argument p does not divide 2^{i} so p|[(a + b) - (c + b)]

so p|(a - c) then p|(2^{i}a - c) so 2^{i}a - c = p(q + r) so 2^{i}a __=__ c mod p

have I done enough to prove the relation and is my arguments logically sound?

Re: help with defining a relation ~ on Z_p

Quote:

Originally Posted by

**bskcase98** ...

reflexive: [a]_{p} ~ [a]_{p} 2^{i}a __=__ 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.

Quote:

Originally Posted by

**bskcase98** symmetric:

...

2^{i}a - b = pq so p|(2^{i}a - b) however p is an odd prime so it can not divide 2^{i} 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$.

Re: help with defining a relation ~ on Z_p

thank you very much for the help