The modulo operation (% in most programming languages) is generally understood as the remainder in integer division. It is easy enough to understand when everything is positive. However, the dividend or divisor can be negative, such cases are not so intuitive anymore. To complicate matters even more, different programming languages have different ways of handling negative number. In this article, I'll try to explain the different ways that programming languages calculate modulo.

Euclidean Division

In Euclidean division, the dividend a, divisor b, quotient q and remainder r satisfy the following equation:

a = bq + r, where a, b, q, r are integers and 0 ≤ r < |b| ¹

When a and b are positive, it is very intuitive. Think of dividing a pizza into a pieces and sharing between b people, let a = 8 and b = 3, ecah person will get 2 pieces (q = 2), and there will be 2 pieces remaining (r = 2).

This equation also works when a or b are negative. For example when a = −7 and b = 3, q = −3 and r = 2. However, our original intuition doesn't work anymore since we can't have negative number of pieces of pizza and negative number of people. To intuitively understand this, we need modular arithmetic.

Modular Arithmetic

Modular arithmetic is a branch of mathematics in which numbers "wrap around" when reaching or exceeding a certain value ². Imagine a clock, initially at 12 o'clock. If we turn the clock back 27 hours, it will be at 9 o'clock, i.e. a = −27, b = 12, q = −3, and r = 9. If we reverse the signs of a and b, the signs of q is reverse and r remains the same.

Python Example

Now we understand how the modulo is calculated, let's try it out in Python.

- 27 % 12

9

No surprise here.

27 % -12

-9

The result is negative! It doesn't follow the equation of Euclidean division! Let's look at Python Documentation to see what's going on. "The modulo operator always yields a result with the same sign as its second operand" ³. So it really doesn't follow Euclidean division. Why doesn't it? Is the implementation wrong?

Congruence

In modular arithmetic, there is a concept called congruence, denoted by a ≡ b (mod m) ⁴. It means that a and b have the same remainder when divided by m. The class of integers that satisfy this relation for a given m is called a congruence class of a mod m. Notice that the remainder in Euclidean division is also in this class, it's the smallest non-negative number. This means it's not incorrect to choose any integer in this class to represent the result of the modulo operation. It's up to each programming language to choose how to implement it.

Implementations in Programming Languages

The value of the modulo depends on how a programming language chooses to do integer division ⁵. In Python, the modulo operation is connected with the floor division (rounding down to a smaller value). For example, 27 // -12 = -3, it is rounded down from -2.25 to -3. Therefore, to satisfy the equation a = bq + r, r will be -9. What is stated in Python's documentation that the sign modulo always follow the sign of the divisor is simply a consequence of satisfying this equation with the quotient calculated with floor division.

Not every programming languages use the floor division for integers. In JavaScript, truncated division is used. Although JavaScript doesn't have an integer division operator, from the the result of the modulo operation, we can work backward to find the result of an integer division. For example, 27 % -12 = 3, we can conclude that q = −2 in the equation a = bq + r. We can see it is rounded towards 0, i.e. trucation. As a consequence of this, the sign of the result of the modulo operation follows the dividend ⁶.

There are others way of implementing modulo, you can see if from this Wikipedia article.

Footnotes