# Thread: Problem with Division Theorem

1. ## Problem with Division Theorem

According to the theorem, it says:
If $a \mid (b)$ and $a \mid (c)$, Then $a \mid mb + nc$ where $m,n \in \mathbb{Z}$

Does this mean $a \mid mb + nc$ where mb=divisor*quotient and nc=remainder?
Or does it mean $a \mid (mb + nc)$, where $a$ divides the whole thing?

Say if I have $m \mid (a-b)$ and $m \mid (c-d)$, I could say this is: $m \mid p(a-b)+q(c-d)$ where $p,q \in \mathbb{Z}$, is this right?

But if I do it the "long way" to get these:
$a=pm+b$
$c=qm+d$
$a+c=m(p+q)+b+d$ Here, the $(b+d)$ is the remainder, right? Sometimes it is hard to see if that it is part of the remainder or the quotient*divisor.

From $a+c=m(p+q)+b+d$, I convert to:
$a+c\equiv b+d \;\;\;\; (mod \; \;m)$
$m \mid a+c-(b+d)$

Here, I don't see $m \mid a+c-(b+d)$ similar to $m \mid p(a-b)+q(c-d)$... Am I not using the theorems correctly?

2. Originally Posted by xEnOn
According to the theorem, it says:
If $a \mid (b)$ and $a \mid (c)$, Then $a \mid mb + nc$ where $m,n \in \mathbb{Z}$

Does this mean $a \mid mb + nc$ where mb=divisor*quotient and nc=remainder?
Or does it mean $a \mid (mb + nc)$, where $a$ divides the whole thing?
The latter.

Say if I have $m \mid (a-b)$ and $m \mid (c-d)$, I could say this is: $m \mid p(a-b)+q(c-d)$ where $p,q \in \mathbb{Z}$, is this right?
Yes.

But if I do it the "long way" to get these:
$a=pm+b$
$c=qm+d$
$a+c=m(p+q)+b+d$ Here, the $(b+d)$ is the remainder, right?
If you mean "b + d is the remainder when a + c is divided by m", then not necessarily because b + d does not have to be less than m. For example,

5 = 1 * 3 + 2
4 = 1 * 3 + 1

Adding these equations, we get 9 = 2 * 3 + 3. Here, 3 is not the remainder when 9 is divided by 3.

From $a+c=m(p+q)+b+d$, I convert to:
$a+c\equiv b+d \;\;\;\; (mod \; \;m)$
$m \mid a+c-(b+d)$

Here, I don't see $m \mid a+c-(b+d)$ similar to $m \mid p(a-b)+q(c-d)$... Am I not using the theorems correctly?
$m \mid a+c-(b+d)$ is correct. It is a special case of $m \mid p(a-b)+q(c-d)$ when p = q = 1.

3. But how come when the equation is in the form of algebra for $a+c=m(p+q)+b+d$, when I convert it to a modulus equation, I get $a+c\equiv b+d \;\;\;\; (mod \; \;m)$, which makes (b+d) the remainder of (a+c) when divided by m?

thanks!

4. The fact that $x\equiv y\pmod{m}$ does not necessarily mean that y is the remainder when x is divided by m. It means that x and y have the same remainder when divided by m. This is also equivalent to the fact that $m\mid (x - y)$. For example, $10\equiv 7\pmod{3}$, but 7 is not the remainder. In fact, the relation $\equiv$ is symmetric, i.e., $x\equiv y\pmod{m}$ implies $y\equiv x\pmod{m}$. So $x\equiv y\pmod{m}$ can't mean that y is the remainder because then x would also have to be the remainder when y is divided by m.

5. Originally Posted by emakarov
The fact that $x\equiv y\pmod{m}$ does not necessarily mean that y is the remainder when x is divided by m. It means that x and y have the same remainder when divided by m. This is also equivalent to the fact that $m\mid (x - y)$. For example, $10\equiv 7\pmod{3}$, but 7 is not the remainder. In fact, the relation $\equiv$ is symmetric, i.e., $x\equiv y\pmod{m}$ implies $y\equiv x\pmod{m}$. So $x\equiv y\pmod{m}$ can't mean that y is the remainder because then x would also have to be the remainder when y is divided by m.
Thanks! I wasn't aware of this. I thought it was merely just representing the remainder.
So that means from , I actually have no way to convert it into this form: , right? So what I did earlier was just a weak assumption that b+d was the remainder because at this point, I wouldn't know if m divides (b+d) has the same remainder as m divides (a+c)?

6. Originally Posted by xEnOn
So that means from , I actually have no way to convert it into this form: , right?
No, a + c = m(p + q) + b + d does imply $a+c\equiv b+d\pmod{m}$. (Not the other way around because the latter equation does not have p + q.)
So what I did earlier was just a weak assumption that b+d was the remainder because at this point, I wouldn't know if m divides (b+d) has the same remainder as m divides (a+c)?
The fact that a + c = m(p + q) + b + d and its corollary, $a+c\equiv b+d\pmod{m}$, do mean that a + c and b + d have the same remainders when divided by m.

If a + c = m(p + q) + b + d, the only reason why b + d may not be the remainder when a + c is divided by m is because b + d may not be smaller than m.

Concerning the OP, you started with m | (a - b) and m | (c - d) and derived two different consequences: m | p(a - b) + q(c - d) and m | a - b + c - d. Both are correct, and the second one is a special case of the first. There is no contradiction or anything surprising.

Also, in the second reasoning, when you said a = pm + b and c = qm + d, you used p and q differently from the first reasoning. It is not surprising that you did not get exactly the same corollary.

7. ahh..Thanks!!