Modulo Operations with Negative Numbers

Here we address the non-obvious question of how the modulo operator works for negative numbers. In particular, we discuss how this works in programming languages.

If you're new to the modulos, check out our dedicated modulo calculator.

Recall that the modulo operator a mod n returns the remainder r of the division of a by n. More formally, in number theory, the result of the modulus operator is an equivalence class, i.e., the whole set of numbers that give the same remainder r when divided by n. In this set, we choose one number as the representative. Most often, this role is played by the remainder of the Euclidean division, which happens to be the smallest non-negative number in the equivalence class.

However, other ways to define the modulo operation are sometimes useful in modular arithmetics, especially when negative integers are involved. (For two positive numbers there's little doubt that the most useful version is that with the positive remainder.) Almost always, we want to have −n < r < n, so the actual choice is between the smallest positive representative and the largest negative one. In programming languages, there are two main implementations of mod, which choose the sign of the result depending on the signs of the dividend a and the divisor n:

• Truncated division returns r = a − n* trunc(a/n). Thus, r has the same sign as the dividend a.
• Floored division returns r = a − n* floor(a/n). Here, r has the same sign as the divisor n.

In most popular programming languages (such as Java, C, C++, Python), there are separate functions that can calculate the modulus according to both these definitions. There are also languages where only one of these operations is available. In case of doubt, consult the documentation before writing any code.

Now, we'll discuss how these two approaches work depending on whether the dividend or the divisor (or both) is negative.

If only the dividend is negative, then:

• Truncated modulo returns the negative remainder; and
• Floored modulo returns the positive remainder.

For instance, let's compute −9 mod 4. Clearly, we have

−9 = 4 * (−2) − 1

and

−9 = 4 * (−3) + 3.

The equality in the first equation corresponds to the truncated division and implies that −9 mod 4 = −1. The dividend is negative, and thus so is the remainder.

The latter equation's equality corresponds to the floored version and implies that −9 mod 4 = 3. The divisor is positive, and thus so is the remainder.

If only the dividend is negative, then:

• Truncated division returns the positive remainder; and
• Floored division returns the negative remainder.

Let's answer the question about 9 mod (−4).

We have 9 = (−4) * (−2) + 1, which corresponds to the truncated version and implies that 9 mod (−4) = 1. The dividend and result are both positive.

Alternatively, 9 = (−4) * (−3) − 3, which is the floored version and gives 9 mod (−4) = −3. The divisor and remainder are negative. See the floor function calculator if you're not yet familiar with it.

If both the divisor and dividend are negative, then both truncated division and floored division return the negative remainder.

Let's discuss (−9) mod (−4).

We have floor(−9/(−4)) = floor(9/4) = 2 and trunc(−9/(−4)) = trunc(9/4) = 2.

Hence, the equality (−9) = (−4) * 2 − 1 corresponds to both truncated and floored division, and implies that in both cases we have (−9) mod (−4) = (−9) − (−4)*2 = (−9) + 8 = −1. The dividend, the divisor, and the remainder are all negative.