Suppose that $d|m$ and that $a≡b \space (mod \space m)$. Explain why it is also true that $a≡b \space (mod \space d)$.
3 Answers
HINT: $a\equiv b\pmod m$ means that $m\mid a-b$, which means that $a-b=km$ for some integer $k$. If $d\mid m$, then $m=dn$ for some integer $n$. Now write down what $a\equiv b\pmod d$ means in terms of divisibility, and you should be able to see pretty quickly why it’s true.
-
$\begingroup$ sigh Downvotes without explanation are singularly unhelpful, especially when applied to correct answers. $\endgroup$ Sep 27, 2012 at 2:48
Try to write things out.
You know that there is some $n$ such that $m=nd$, you also know that, $a=sm+r=(sd)n+r$ and $b=s'm+r=(s'd)n+r$. Hence what you wanted to prove.
The idea of "writing things out"often works for problems like these.
Hint $\rm\,\ d\:|\:m\:|\:a\!-\!b\ \Rightarrow\ d\:|\:a\!-\!b\ $ by transitivity of "divides".
Remark $\ $ Transitivity of divides is true because $\Bbb Z$ is closed under multiplication
$$\rm \frac{m}d,\, \frac{c}m\,\in\,\Bbb Z\ \Rightarrow\ \frac{c}d = \frac{m}d \frac{c}m\,\in\,\Bbb Z$$
$$\rm d\:|\:m,\ \ m\:|\:c\ \ \Rightarrow\ d\:|\:c\qquad\qquad\ \ \ $$
Yours is simply the special case where $\rm\: c = a - b.$
In fact all the common laws of divisibility are relational translations of the operational laws stating that $\rm\:\mathbb Z\:$ forms a subring of its fraction field $\rm\:\mathbb Q\:.\:$ More generally, given any subring $\rm\:Z\:$ of a field $\rm\:F\:$ we define divisibility relative to $\rm\ Z\ $ by $\rm\ x\ |\ y\ \iff\ y/x\in Z\:.\:$ Then the above proof still works, since $\rm Z$ is closed under multiplication. In other words, the usual divisibility laws follow from the fact that rings are closed under the operations of subtraction and multiplication; being so closed, $\rm\:Z\:$ serves as a ring of "integers" for divisibility tests.
For example, to focus on the prime $2$ we can ignore all odd primes and define a divisibility relation so that $\rm\ m\ |\ n\ $ if the power of $2$ in $\rm\:m\:$ is $\le$ that in $\rm\:n\:$ or, equivalently if $\rm\ n/m\ $ has odd denominator in lowest terms. The set of all such fractions forms a ring $\rm\:Z\:$ of $2$-integral fractions. Moreover, this ring enjoys parity, so arguments based upon even/odd arithmetic go through. Similar ideas lead to powerful local-global techniques of reducing divisibility problems from complicated "global" rings to simpler "local" rings, where divisibility is decided by simply comparing powers of a prime.
See also this post which discussed the gcds and lcms of rationals (fractions) from this perspective.