Show whether a relation R is transitive for xRy iff 3|(2x+y)

Question

Define a relation

$$R : Z^+ \rightarrow Z^+$$

by xRy iff (2x+y)mod3=0.

R is reflexive: Let x=y. So (x,x) is in R. Then we have 2x+x=3x, and since x is an integer, it must clearly be divisible by 3.

R is not antisymmetric, by counterexample:

$$[(2,5) \land (5,2) \in R] \land 5 \neq 2$$

R is symmetric, since 2x+y = 3i, 2x+x = 3x & 2y+y = 3y; to show symmetry, 2y+x must also be divisible by 3;

so 2x+y + 2y+x = 3x + 3y, with 2x+y = 3i,

2y+x = 3x+3y - 2x+y = 3x+3y - 3i = 3(x+y+i)

Now how to show that it is transitive? I need to show that for any xRy and yRz, xRz. So 2x+y = 3m and 2y+z = 3n where m,n are integers. Solving for y in the second equation, y = (3n-z)/2. Plugging that into the first, we have 2x + (3n-z)/2 = 3m, so 2x - z/2 = 3m - (3n)/2; *2: 4x - z = 6m - 3n. Which is ok, except I need 2x + z, not 4x - z =\

Answer 1

Suppose $3\mid 2x+y$ and $3\mid 2y+z$; then $$ 3\mid (2x+y)+(2y+z) $$ or $$ 3\mid (2x+z)+3y. $$ Since $3\mid 3y$, you conclude that $3\mid 2x+z$.

Note that this is congruence modulo $3$ in disguise: saying $3\mid 2x+y$ is equivalent to saying that $3\mid 2x+y-3x$, that is, $3\mid y-x$.

Answer 2

If $3 \mod c = 0$ for some $c$, then $c$ must be a factor of 3. So, if $x$R$y$, then either $2x + y = 1$ or $2x + y = 3$. The only two cases are $x = y = 1$ and $x = 0, y = 1$. So if $x$R$y$ and $y$R$z$, then $x$R$z$, because it must be that $z = 1$ and we know $x = 0$ or $x = 1$.