Question about $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$

Question

So Knuth's 'Discrete Mathematics' states that:

$a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$ if $m$ and $n$ are relatively prime.

But being a curious human being that I am a tried to prove that and here's my attempt:

$x \equiv y \pmod{mz} \Leftrightarrow \exists_{k \in \mathbb{Z}} kmz = y - x \Leftrightarrow \exists_{l \in \mathbb{Z}} lm = y - x \Leftrightarrow x \equiv y \pmod{m}$, because i put $l=km$.

I can do the same for $z$ and I get that $x \equiv y \text{ (mod z) }$.

Everything came up roses yet I've never used the fact, that $m$ and $z$ are relatively prime. Is my proof incorrect or isn't it necessary for $m$ and $z$ to be relatively prime?

Answer 1

The second equivalence in your proof is not correct; that is, $(\exists k \in \mathbf{Z}) (kmz = y -x)$ is not equivalent to $(\exists l \in \mathbf{Z})(lm = y-x)$. You only have $$(\exists k \in \mathbf{Z}) (kmz = y -x) \implies (\exists l \in \mathbf{Z})(lm = y-x).$$.

Which "Discrete Mathematics" book by Knuth is this? Do you mean "Concrete Mathematics" with Graham and Patashnik?