prove transitivity property congruence mod m

Question

Prove transitivity property of congruence mod m. Show that if $x\equiv y \pmod m$ and $y \equiv z\pmod m$ then $x\equiv z\pmod m$ .

I didn't really get the tutors explanation of this, I get what transitivity is but the congruence mod m confused me... can someone go through it in-depth for me?

Answer 1

Utilize the fact that

$$x-z=\underbrace{x-y}+\underbrace{y-z}$$

Can you prove $\displaystyle a\equiv b,c\equiv d\pmod m\implies ac\equiv bd\pmod m?$

Answer 2

$x\equiv y \pmod m$ means that $x-y =km$ for some integer $k$. With the same way we have $y-z=nm$ for an in integer $n$.

Substrat the last from the first to get $x-z=(k-n)m$ which means that $x\equiv z \pmod m$.

Answer 3

Usually the best way to start a problem like yours is to carefully expand out the definitions.

1. $x\equiv y\bmod m$ means $m$ divides $x-y$,
2. $y\equiv z\bmod m$ means $m$ divides $y-z$, and
3. $x\equiv z\bmod m$ means $m$ divides $x-z$.

If $m=2$, for instance, these definitions say that $x-y$, $y-z$, and $x-z$ are even.

To prove the transitivity property, we need to assume that 1 and 2 are true and somehow conclude that 3 is true. 1 and 2 say that $m$ divides $x-y$ and $y-z$. We want to show that $m$ divides $x-z$. Okay. Well, whenever $m$ divides two numbers it has to divide their sum. For instance, the sum of two even numbers is always an even number. It follows that $m$ divides the number $(x-y) + (y-z)$. But $(x-y) + (y-z) = x-z$, so $m$ divides $x-z$. That is what we set out to show.

To write the proof up carefully, you would need to explain in detail why the sum of two numbers divisible by $m$ is itself divisible by $m$.

When you do enough problems like this, you start to see that there are only a few "moves" that it is possible to make. The only things that 1 and 2 give us are two numbers that are multiples of $m$ -- that's not a lot to go on. So why not see what happens when we add them together? That addition is the stroke of luck that finishes the problem.