Why is -101 mod 13 = 3 and not 10

[Superdemongob]

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.

 

[dextercioby]

So you have that $-101\equiv -10 ~\mbox{mod} ~13$

So $-10 = 13 (-1) + 3$, right ?

 

[Superdemongob]

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 $-101\equiv -10 ~\mbox{mod} ~13$ because you know that the remainder will be the same?

 

[haruspex]

is the reason you know that $-101\equiv -10 ~\mbox{mod} ~13$ because you know that the remainder will be the same?

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.

 

[rcgldr]

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.

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).

 

[Mensanator]

So you have that $-101\equiv -10 ~\mbox{mod} ~13$

So $-10 = 13 (-1) + 3$, right ?

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.