1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mod Arithmatic

  1. Jun 19, 2010 #1

    Just a simple Mod question.

    Is (ka)mod kb = k(a mod b)?

  2. jcsd
  3. Jun 19, 2010 #2


    User Avatar
    Science Advisor

    (ka) mod kb is the remainder when ka is divided by kb. Obviously, ka/kb= a/b and so has the same remainder as a divided by b. Therefore, the answer to your question is "no". What is true is that (ka) mod kb= a mod b.
  4. Jun 19, 2010 #3
    perhaps a counter example to your reply...

    15 mod 9 = 6
    5 mod 3 = 2
    3(5 mod 3) = 6
  5. Jun 19, 2010 #4
    Yes I do believe I am correct. Suppose
    ka mod kb = c
    a mod b = d
    then this means that
    ka = Z(kb)+c
    a = Z(b)+d
    where Z is an integer
    Hence c/k=d, and if this is true then
    ka mod kb = c = kd = k(a mod b)

    Thank you for your reply anyway.
  6. Jun 20, 2010 #5
    This is a special case.
    [itex]ka=Z(kb)+c[/itex] and [itex]a=Z'(b)+d[/itex],where[itex]Z,Z'\in\mathbb Z[/itex]
    But generally,[itex]Z\not =Z'[/itex]
    Last edited: Jun 20, 2010
  7. Jun 21, 2010 #6
    No I dont think so.

    We have
    ka=(kb)Z+c where 0<c<kb
    a = bZ'+d where 0<d<b
    multiplying the second equation by k we arrive at
    ka = kb Z' +kd
    kb Z +c = kb Z'+kd
    Hence the right hand side must be an integer. But since both kd and c are in (0,kb), the distance between them kd-c cannot be larger than kb. so it must be zero.
    Giving us Z=Z'
  8. Jun 21, 2010 #7
    First, your equality can only be valid for [itex]k\geq 0[/itex]. Second, everyone seems to be forgetting the remainder theorem: for b,a in Z, there are unique integers q and r, such that:
    b = aq + r, 0 \leq r <\left|a\right|

    b=aq + r \Rightarrow kb = \left(ka\right)q + kr

    But, as [itex]0 \leq r <\left|a\right|[/itex] and [itex]k \geq 0[/itex] then [itex]0 \leq kr <\left|ka\right|[/itex], which means that (by uniqueness) kr is the remainder of kb divided by ka, hence:

    (kb mod ka) = kr = k(a mod b), [itex]k\geq 0[/itex]
    Last edited: Jun 22, 2010
  9. Jun 22, 2010 #8
    2*7 mod 2*3 = 2
    7 mod 3 = 1

  10. Jun 22, 2010 #9
    Sorry. There was a typo in the last equality; it's corrected now.

    2*7 mod 2*3 = 2(7 mod 3) = 2
  11. Jul 7, 2010 #10
    Not true...
    Suppose a=12, b=5, k=8
    Then you have, ka=96, kb=40

    Sure, a/b=2.4 and ka/kb=2.4

    But, a mod b = 2 whereas (ka) mod (kb) = 16

    And, by the way, the answer (if it was unclear by reading through this thread), is "yes"
    k * (a mod b) = (ka) mod (kb) for ALL a, b, k such that k<>0 and b<>0 (otherwise, you will have a divide-by-zero error)
  12. Jul 7, 2010 #11
    Here's the proof...

    Let's first assume that the symbol, [tex]\odot[/tex] is the operator for the function "mod"
    and that the function "int" returns an integer which rounded down from it's argument; for example, int(8.9) = 8, but int(-8.9)= -9

    [tex]a \odot b = a - int \left( \frac{a}{b} \right) * b[/tex] (this is the definition of the mod function)

    [tex]k * ( a \odot b) = k * \left( a - int \left( \frac{a}{b} \right) * b \right) = ka - int \left( \frac{a}{b} \right) * kb[/tex]

    [tex] (ka) \odot (kb) = (ka) - int \left( \frac{ka}{kb} \right) * kb[/tex]

    but since [tex]\frac{ka}{kb} = \frac{a}{b}[/tex]

    we have

    [tex] (ka) \odot (kb) = (ka) - int \left( \frac{a}{b} \right) * kb[/tex]

    which has already been shown to be equal to [tex]k * (a \odot b)[/tex]
    Last edited: Jul 7, 2010
  13. Jul 7, 2010 #12
    I found the above terribly painful, but completely correct. To prove your deal, just use the euclidean algorithm. Write
    a = q\cdot b + r,
    where [itex]q[/tex] is the quotient and [itex]r[/itex] is the remainder ([itex]0\leq r< |b|[/itex]). Then, just multiply everything by [itex]k.[/itex]

    In fairness, this is just zgozvrm proof with less abusive notation. Note that Halls of Ivy just confused the quotient with the reminder.
  14. Aug 28, 2010 #13
    Thank you all for your replies.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook