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!

Why is -101 mod 13 = 3 and not 10

  1. Oct 21, 2012 #1
    This is a very basic question that I am having some difficulty grasping.

    When I do the long division for -101 / 13, my first step is -7 which comes out to -91 and so I have left -10.

    Shouldn't this be where the calculation stops?

    One of the thoughts I had was that as -13 is smaller than -10, I should go one step further and subtract -13 from -10 to get +3. and that's why the mod is 3.

    If that is correct, could someone please explain why?
    If that is incorrect, could someone please explain how we get 3 instead of 10?

    Thanks for any help.
  2. jcsd
  3. Oct 21, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    So you have that [itex] -101\equiv -10 ~\mbox{mod} ~13 [/itex]

    So [itex] -10 = 13 (-1) + 3 [/itex], right ?
  4. Oct 21, 2012 #3
    EDIT: I totally just got it. Thank you so much for your prompt response.

    Sorry, i know that i'm being really thick on this and once i see it i'll kick myself but 1 follow up question if you don't mind.

    is the reason you know that [itex] -101\equiv -10 ~\mbox{mod} ~13 [/itex] because you know that the remainder will be the same?
    Last edited: Oct 21, 2012
  5. Oct 21, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Not sure what you mean by the question, but -101 + 13*7 = -10, so they must be the same mod 13 (and mod 7).
    Btw, there are programming languages that get modulo of negative numbers 'wrong' (from a mathematician's perspective). Very annoying.
  6. Oct 21, 2012 #5


    User Avatar
    Homework Helper

    The normal convention for modulo is that the sign of the result is the same as the sign of the divisor. This means that the range of modulo 13 is limited to the set of 13 numbers {0, 1, 2, ... , 10, 11, 12}, none of them negative.

    To continue with this line of thinking, then -101 / 13: results in a quotient of -8 with a remainder of +3.

    Similary, the range of modulo -13 is (-12, -11, -10, ... -2, -1, 0}, so 101 / (-13) results in a quotient of -8 and remainder -3.

    So using this model, quotients are always rounded down towards -∞, instead of towards zero. Older computers with signed non-restoring divide algorithm performed division in this manner, but I'm not aware of any current computers that do this. The computer language APL, implements modulo as described above.

    One advantage of using this convention is that it's is origin independent, let a, b c, n, and q be integers:

    if a mod b = c, then (a ± n b) b mod = c

    if a / b = q, then (a ± n b) / b = q ± n

    This wouldn't hold true if quotients didnt round down towards -∞, and c was not restricted to have the same sign as b (or be equal to zero).
    Last edited: Oct 21, 2012
  7. Oct 21, 2012 #6
    Suppose you had a 13 hour clock, labeled 0 to 12. Start at 0 and go counterclockwise 104
    hours (since you went counterclockise, that's -104 hours. Youl'll find
    yourself ack at 0 (since 104/13=8). But wait, we
    went too far, so go clockwise 3 hours and we'll see that the clock
    reads 3 for -101 hours.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook