# Why is -101 mod 13 = 3 and not 10

1. Oct 21, 2012

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

2. Oct 21, 2012

### dextercioby

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

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

3. Oct 21, 2012

### 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?

Last edited: Oct 21, 2012
4. Oct 21, 2012

### haruspex

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.

5. Oct 21, 2012

### rcgldr

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
6. Oct 21, 2012

### Mensanator

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