Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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: $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.

share|cite|improve this answer
sigh Downvotes without explanation are singularly unhelpful, especially when applied to correct answers. – Brian M. Scott Sep 27 '12 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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.