# How does 9 mod -7 = -5?

Forgive me if this question does not belong on this site for it is simplistic and this is my first post, however I do not seem to understand the modulo function when it comes to negative numbers.

I'd assume the process for calculating modulo would be the same as with positive numbers:

• 9 % 7 = 2 because 9 - (7 * 9/7) = 9 - (7 * 1) = 2

So wouldn't 9 % (-7) = 9 - (-7 * -9/7) = 9 - (-7 * -1) = 2?

• it's because modulo n is always between 0 and said n. – Dleep May 16 '15 at 2:56

Note that $-5 = -7 +2$ and $9 = -(-7)+2$. When you do these calculations, your remainder is always nonnegative by definition (just to make things easily stated) but your coefficient $q$ (in $p = qd+r$) can be any number in $\Bbb Z$. This is why $-1$ is admissible as a coefficient in front of $-7$ when decomposing $9$.

Recall that $a \equiv b \bmod n$ if and only if $n$ divides $a - b$. This is the definition.

So is it true that $-5 \equiv 9 \bmod -7$?

It's absolutely true that $9\equiv 2\bmod (-7)$. It's also true that $9\equiv -5\bmod (-7)$, and also $9\equiv 9\bmod (-7)$, $9\equiv 16\bmod (-7)$, etc.

I suspect you're being confused by the output from a computer. The output that a computer makes when the symbols 9 % -7 are entered into it might reflect whatever conventions a programmer decided on (e.g., this StackOverflow post).

• Yes I initially was computing 9%7 on google and then decided to try 9%-7 to which I got the bewildering response -5. – rivanov May 16 '15 at 3:08
• @rivanov Just to be clear $x \bmod -7$ is exactly the same as $x \bmod 7$. So if you're ever confused by the negative modulus, just switch to positive -- there is no difference. – user137731 May 16 '15 at 3:17

There are various conventions for how to define the quotient and remainder for the division algorithm when extended from naturals to integers. The remainder is uniquely determined once one defines the quotient, and usually conventions say which to round the quotient, e.g. towards $\,0\,$ or, towards the nearest integer, or towards $\,\pm\infty.$ Some programming languages provide all of the possibilities, e.g. see the floor, ceiling, round, truncate functions in Common Lisp.

A web search will turn up much further discussion in many places, e.g. see Wikipedia and see also D. Leijen, Division and Modulus for Computer Scientists.

The precise definition of the Modulo function (mod) is such that $a\bmod (n)=b$ if $a-b$ is an integer multiple of $n$.

In your case $a=9$, $b=-5$ and $n=-7$ so $a-b=9-(-5)=14$, which is indeed an integer multiple of $n=-7$.

So by definition $9\bmod (-7)$ must equal $-5$.