help with defining a relation ~ on Z_p

**bskcase98** · October 16th 2012, 06:58 PM

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ⁱ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ⁱ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ⁱa = b mod p and 2ⁱb = a mod p but I am unsure if the logic is sound.
2ⁱa = b mod p then 2ⁱa = pq + b for some integer q
2ⁱa - b = pq so p|(2ⁱa - b) however p is an odd prime so it can not divide 2ⁱ so p|(a - b) and p|(b - a) then p|(2ⁱb - a)
then 2ⁱb - a = pq so 2ⁱb = a mod p

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

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

**johnsomeone** · October 16th 2012, 07:52 PM

Originally Posted by bskcase98

...
reflexive: [a]_p ~ [a]_p 2ⁱ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 $2^0a = a \mod p$ . That's what shows that a ~ a.

Originally Posted by bskcase98

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

**bskcase98** · October 17th 2012, 02:32 AM

thank you very much for the help

Thread: help with defining a relation ~ on Z_p

LinkBack

Thread Tools

Display

help with defining a relation ~ on Z_p

Re: help with defining a relation ~ on Z_p

Re: help with defining a relation ~ on Z_p

Similar Math Help Forum Discussions

For the following relation, show that R is an equivalence relation and determine the.

defining an operator - 2

Defining an operaor

Defining a plane

Defining the p.m.f. of X

Search Tags