How to do modular arithmetic with a negative n

Question

Playing with Python and the mod operation I encountered that (5 % -3) = -1. This is confirmed by WolframAlpha, and I have not been able to find any simple explanation for this online, mostly because all I can find about modular arithmetic uses a positive n.

I am surprised by this result. My understanding of the modulo operation is that a mod n is a number c computed by taking the integer part q = a / n, and then substracting n·q from a.

Therefore, for 5 mod -3 I would do:

1. q = int(5 / -3) = int(-1.6667) = -1
2. 5 - (-3)·(-1) = 5 - 3 = 2

Where am I wrong?

I have realised that -1 is congruent with 2 modulo -3, so maybe the answer is that the result must be between 0 and n, so if n is negative we need to add n to the positive result, but not sure if this is really the reason.

Please consider that I am not a mathematician, so the simpler the explanation the better.

Answer 1

An integer is divisible by 3 if and only if it is divisible by -3. The usual definition of congruence mod 3 is that $a\equiv_3 b$ if and only if $3\mid a-b$ (i.e if and only if $a-b$ is divisible by 3). So you have the same structure mod 3 and mod -3. The reason they didnt give you 2 as your answer is probably because they want to choose representatives from the set $\{0,-1,-2\}$.

Answer 2

There is nothing wrong with the two answers $-1$ and $2$. These are the same modulo $-3$.

Note that $-1=2+(-3)$.