# Modulo Operations with Negative Numbers

It's not obvious **how the** **modulo** **operator works for negative** numbers. In this article, we discuss this question, and particularly how it all works in programming languages.

## How does modulo work with negative numbers?

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.

## When only the dividend 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.

## When only the divisor is negative

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.

## When both the divisor and dividend are negative

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.