Results 1 to 7 of 7

Thread: Problem with Division Theorem

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    Problem with Division Theorem

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

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

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

    But if I do it the "long way" to get these:
    $\displaystyle a=pm+b$
    $\displaystyle c=qm+d$
    $\displaystyle a+c=m(p+q)+b+d$ Here, the $\displaystyle (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 $\displaystyle a+c=m(p+q)+b+d$, I convert to:
    $\displaystyle a+c\equiv b+d \;\;\;\; (mod \; \;m)$
    $\displaystyle m \mid a+c-(b+d)$

    Here, I don't see $\displaystyle m \mid a+c-(b+d)$ similar to $\displaystyle m \mid p(a-b)+q(c-d)$... Am I not using the theorems correctly?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    Quote Originally Posted by xEnOn View Post
    According to the theorem, it says:
    If $\displaystyle a \mid (b)$ and $\displaystyle a \mid (c)$, Then $\displaystyle a \mid mb + nc$ where $\displaystyle m,n \in \mathbb{Z}$

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

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

    But if I do it the "long way" to get these:
    $\displaystyle a=pm+b$
    $\displaystyle c=qm+d$
    $\displaystyle a+c=m(p+q)+b+d$ Here, the $\displaystyle (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 $\displaystyle a+c=m(p+q)+b+d$, I convert to:
    $\displaystyle a+c\equiv b+d \;\;\;\; (mod \; \;m)$
    $\displaystyle m \mid a+c-(b+d)$

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

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

    thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    The fact that $\displaystyle 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 $\displaystyle m\mid (x - y)$. For example, $\displaystyle 10\equiv 7\pmod{3}$, but 7 is not the remainder. In fact, the relation $\displaystyle \equiv$ is symmetric, i.e., $\displaystyle x\equiv y\pmod{m}$ implies $\displaystyle y\equiv x\pmod{m}$. So $\displaystyle 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    Posts
    95
    Quote Originally Posted by emakarov View Post
    The fact that $\displaystyle 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 $\displaystyle m\mid (x - y)$. For example, $\displaystyle 10\equiv 7\pmod{3}$, but 7 is not the remainder. In fact, the relation $\displaystyle \equiv$ is symmetric, i.e., $\displaystyle x\equiv y\pmod{m}$ implies $\displaystyle y\equiv x\pmod{m}$. So $\displaystyle 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)?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    Quote Originally Posted by xEnOn View Post
    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 $\displaystyle 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, $\displaystyle 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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2010
    Posts
    95
    ahh..Thanks!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. division theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 18th 2009, 10:34 AM
  2. least common multiple and division theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 6th 2009, 11:20 AM
  3. [SOLVED] long division/ Remainder Theorem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Feb 12th 2009, 04:09 PM
  4. Division Theorem for Polynomials...
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: Apr 21st 2008, 05:09 PM
  5. long division using the remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 22nd 2005, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum