Equalities modulo a product hold modulo a factor Is it safe to assume that if $a\equiv b \pmod {35 =5\times7}$
then $a\equiv b\pmod 5$  is also true?
 A: 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$.
A: 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
$$
A: $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.
