Results 1 to 7 of 7

Math Help - Problem with Division Theorem

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Quote Originally Posted by xEnOn View Post
    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.
    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 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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    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.
    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 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)?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    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 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.
    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: September 18th 2009, 10:34 AM
  2. least common multiple and division theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 6th 2009, 11:20 AM
  3. [SOLVED] long division/ Remainder Theorem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: February 12th 2009, 04:09 PM
  4. Division Theorem for Polynomials...
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: April 21st 2008, 05:09 PM
  5. long division using the remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 22nd 2005, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum