Negative remainder vs modulo

What is the remainder of dividing $7$ by $-3$? In fact, it can be $1$ or $-2$, depending on the chosen convention and/or programming language in use.

What? Negative reminders? Let’s look at this in detail.

Division in mathematics

In mathematics, division is fundamentally about splitting a quantity into equal parts.

When we divide a number $a$ by another number $b$, we’re asking: “How many $b$’s can we fit into $a$?”

Euclidean division

Euclidean division a.k.a. integer division is specifically a type of division applied to integers.

Let’s look at the formula: $$ a=b*q+r $$

Here, we have:

• dividend ($a$): the number being divided
  • e.g., in $7 / 3$, the dividend is $7$
• divisor ($b$): the number you divide by
  • e.g., in $7 / 3$, the divisor is $3$

Euclidean division gives us two important values when dividing integers:

• integer quotient ($q$): the division gives a whole number result (rounding down)
  • e.g., $7 / 3$ has a quotient of $2$
• integer residue ($r$): the leftover part after the division is an integer
  • e.g., $7 - (3 * 2) = 1$

Moreover, this must be true: $$ b \neq 0 \\[1em] 0 \leq r < |b| \\[1em] 0 \leq residue < |divisor| \quad \text{← same as above} $$

Look carefully:

• $b$ can be negative, but can’t be $0$
• $r$ is a positive number less than absolute value $|b|$ (divisor) and can be $0$.

Euclidean division examples for pure math

Let’s look at how pure math will handle all the cases:

• Positive dividend, positive divisor: $$ 7 \bmod 3 = 1 \\ 7 = 3 * 2 + 1 $$

• Positive dividend, negative divisor: $$ 7 \bmod (-3) = 1 \\ 7 = (-3) * (-2) + 1 $$

• Negative dividend, positive divisor. Pay attention that we find quotient ($-3$) so the result ($-9$) is less than dividend ($-7$): $$ -7 \bmod 3 = 2 \\ -7 = 3 * (-3) + 2 $$

• Negative dividend, negative divisor. Pay attention that we find quotient ($3$) so the result ($-9$) is less than dividend ($-7$): $$ (-7) \bmod (-3) = 2 \\ -7 = (-3) * 3 + 2 $$

As you see, we round down the result of $quotient * divisor$ even for the negative numbers, hence the remainder is positive in math (in most of the conventions).

Modulo vs Congruence modulo

The remainder can be computed using the modulo operation: $$ r = a \bmod b $$

It’s important not to confuse modulo operation and congruence modulo relation.

Congruence modulo relation denoted as: $$ a \equiv b \pmod{m} $$

and essentially means that: $$ a \bmod m = b \bmod m $$

In other words: $a$ and $b$ gives the same remainder when divided by $m$.

Remainders in programming

As we saw earlier, in math, the remainder is a positive number (again, in most of the conventions).

However, the operation of computing the remainder in programming languages can return a negative result (for a negative dividend or divisor).

There are two options here:

• The sign of the remainder matches with the sign of the dividend
  • The incomplete quotient rounds to $0$.
• The sign of the remainder matches with the sign of the divisor
  • The incomplete quotient rounds to $−\infty$.

Let’s break down each case below.

Remainder sign = dividend sign

The incomplete quotient rounds to the direction of $0$.

Let’s look at the cases:

• Positive dividend, positive divisor: $$ 7 \bmod 3 = 1 \\[1em] 7 / 3 = 2.333(3) \approx 2 \quad \text{rounding to $0$} \\[1em] 7 = 3 * 2 + 1 $$

• Positive dividend, negative divisor: $$ 7 \bmod (-3) = 1 \\[1em] 7 / (-3) = -2.333(3) \approx -2 \quad \text{rounding to $0$} \\[1em] 7 = (-3) * (-2) + 1 $$

• Negative dividend, positive divisor. You see that the quotient is $-2$ here, not $-3$, like in regular math: $$ (-7) \bmod 3 = -1 \\[1em] (-7) / 3 = -2.333(3) \approx -2 \quad \text{rounding to $0$} \\[1em] -7 = 3 * (-2) + (-1) $$

• Negative dividend, negative divisor. You see that the quotient is $2$ here, not $3$, like in regular math: $$ (-7) \bmod (-3) = -1 \\[1em] (-7) / (-3) = 2.333(3) \approx 2 \quad \text{rounding to $0$} \\[1em] -7 = (-3) * 2 + (-1) $$

Remainder sign = divisor sign

The incomplete quotient rounds to the direction of $−\infty$.

Let’s look at the cases:

• Positive dividend, positive divisor: $$ 7 \bmod 3 = 1 \\[1em] 7 / 3 = 2.333(3) \approx 2 \quad \text{rounding to $−\infty$} \\[1em] 7 = 3 * 2 + 1 $$

• Positive dividend, negative divisor. You see that the quotient is $-3$ here, not $-2$, like in regular math: $$ 7 \bmod -3 = -2 \\[1em] 7 / (-3) = -2.333(3) \approx -3 \quad \text{rounding to $−\infty$} \\[1em] 7 = (-3) * (-3) + (-2) $$

• Negative dividend, positive divisor: $$ -7 \bmod 3 = 2 \\[1em] -7 / 3 = -2.333(3) \approx -3 \quad \text{rounding to $−\infty$} \\[1em] -7 = 3 * (-3) + 2 $$

• Negative dividend, negative divisor. You see that the quotient is $2$ here, not the $3$, like in regular math: $$ (-7) \bmod (-3) = -1 \\[1em] (-7 / (-3) = 2.333(3) \approx 2 \quad \text{rounding to $−\infty$} \\[1em] -7 = (-3) * 2 + (-1) $$

‼️ As you see, both cases in computer science (matches the sign of dividend and matches the sign of divisor) are different from pure math principles.

Implementation details

It’s important to note that the behavior of the remainder operation vary depending on the programming language.

Some languages round towards zero, while others round towards negative infinity.

There are two types of division:

• Truncating division: $3.75$ equals $3$, and $-3.75$ equals $-3$.
• Floor division: $3.75$ equals $3$, but $-3.75$ equals $-4$ (round down, Math.floor())

Java implementation

In Java, the modulo operation (%) follows the rule where the remainder takes the sign of the dividend (the first operand).

Java’s modulo operation is defined by the formula:

a % b = a - (a / b) * b

where / is integer (truncating) division that rounds toward zero.

Python implementation

In Python, the modulo operator (%) follows the rule where the remainder takes the sign of the divisor (the second operand).

Python’s modulo operation is defined by the formula:

a % b = a - (a // b) * b

where // is floor division that rounds toward negative infinity.

Practical applications

One may ask – wait, why do we need multiple ways to compute remainders?

Well, each of the ways has its real-life applications.

Remainder sign = dividend sign

There is a number of n cents, positive or negative. One needs to convert it to dollars and cents. It will be:

dollars = n div 100
cents = n mod 100

The sign of the remainder coincides with the sign of the dividend.

Remainder sign = divisor sign

There is an infinite grid of cells, each cell is 16×16 pixels. Which cell does the point (x, y) fall into, and what are its coordinates relative to the top-left corner of the cell? The answer:

x div 16, y div 16
// and
(x mod 16, y mod 16)

The sign of the remainder matches the sign of the divisor.

Cross-Language modulo behavior

Since each language has both types of division, we can program each modulo behavior in each language.

Python:

python_mod = a - (a // b) * b  # floor division
java_mod = a - int(a / b) * b  # truncating division

Java:

// floor division
int pythonMod = (int) (a - Math.floor((double) a / (double) b) * b);

// truncating division
int javaMod = a - (a / b) * b; 

Positive remainder implementation

But what if we need the remainder always to be positive in programming?

We can’t just take absolute value, since you remember, that negative remainder means we are “on the other side” from the destination target.

There is a common technique to ensure that the result of the modulo operation is always in the non-negative range [0, a-1], regardless of how the modulo operation is implemented in a particular language or context: $$ (a \bmod b + b) \bmod b $$

Let’s break it down:

1. a mod b: this computes the initial remainder. This could be negative (e.g., $-1 \bmod 5$ might return $-1$ in some contexts) or positive
2. + b: this shifts negative results into the positive range. For example, $-1 + 5 = 4$
3. mod b: even if the remainder was positive originally, this ensures the final result is still within [0, a-1].

Let’s look closer:

1. a mod b:
   • In Java -1 mod 5 = -1.
   • In Python -1 mod 5 directly returns $4$.
2. + b:
   • If the first result was $-1$: $-1 + 5 = 4$ (now a positive value).
   • If the first result was already $4$: $4 + 5 = 9$ (temporarily exceeds the modulus range).
3. mod b:
   • If you had $4$ from the first step: 4 mod 5 = 4 (no change).
   • If you had $9$ from the first step: 9 mod 5 = 4 (brings it back into the range [0, 4]).