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
    Hi

    Just a simple Mod question.

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

    Thanks
     
  2. jcsd
  3. Jun 19, 2010 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    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
    but
    3(5 mod 3) = 6
     
  5. Jun 19, 2010 #4
    Yes I do believe I am correct. Suppose
    ka mod kb = c
    and
    a mod b = d
    then this means that
    ka = Z(kb)+c
    and
    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
    and
    a = bZ'+d where 0<d<b
    multiplying the second equation by k we arrive at
    ka = kb Z' +kd
    so
    kb Z +c = kb Z'+kd
    kb(Z-Z')=kd-c
    (Z-Z')=(kd-c)/kb
    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:
    [tex]
    b = aq + r, 0 \leq r <\left|a\right|
    [/tex]

    Therefore:
    [tex]
    b=aq + r \Rightarrow kb = \left(ka\right)q + kr
    [/tex]

    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)

    Therefore,
    [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]

    Then,
    [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
    [tex]
    a = q\cdot b + r,
    [/tex]
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Mod Arithmatic
  1. A mod b (Replies: 7)

  2. Mod Function Inverse (Replies: 6)

Loading...