0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

$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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?$

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.