# Congruences, elementary number theory

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

-
Um, what is $l$? If $d=l=6$ and $m=5, a=1, b=6$, then it isn't true. Did you mean $d\mid m$? –  Thomas Andrews Sep 26 '12 at 19:50
Sorry, yes meant to say $d|m$. –  Swine.Flu Sep 26 '12 at 19:52

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.

-

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

-
sigh Downvotes without explanation are singularly unhelpful, especially when applied to correct answers. –  Brian M. Scott Sep 27 '12 at 2:48