Equalities modulo a product hold modulo a factor

Question

Is it safe to assume that if $a\equiv b \pmod {35 =5\times7}$

then $a\equiv b\pmod 5$ is also true?

Answer 1

The statement "$a \equiv b \text{ mod m}$" is equivalent to "There exists integer k such that $a = b + km$". If there exists $k_1$ such that $a = b +35k_1$, then we can set $k_2=7k_1$, and then $a = b+ 5k_2$. So $a \equiv b \text{ mod 35}$ does in fact imply $a \equiv b \text{ mod 5}$. This also follows trivially from the Chinese Remainder Theorem: if $a$ and $b$ represent the same element in Z$_{35}$, then they also represent the same element in Z$_5$x Z$_7$.

Answer 2

If $m | c$ and $c | a -b$, then $m |a -b$. Use this and the fact that

$$ a \equiv b \pmod{d} \iff d | a - b $$

Answer 3

$a \equiv b \mod mn \implies mn|a-b$ and as $m|mn$ and $mn|a-b$ then $m|a-b$ so $a\equiv b \mod m$.

(Lemma: Divisibility is transitive. Pf: $a|b$ means there exists an integer, $k$, so that $ak = b$. $b|c$ means there exists an integer, $j$ so that $bj =c$. So $a(jk)=c$. So $a|c$.)

It does not work the other way, of course. $a\equiv b \mod m \not \implies a\equiv b \mod m$ but we can state:

$a \equiv b \mod m \implies a \equiv b + km \mod mn$ for some $k;0 \le k < n$. (And by Chinese Remainder theorem we know said $k$ is unique.