It may come as a surprise but not all integer divisions are the same. Perhaps because we are used to operate mostly with positive numbers, we don’t pay too much attention to what happens when the modulo operator is used with negative integers.

If you calculate the integer division of 7/3 in your favourite programming language, no doubt you’ll get 2. And if you calculate the corresponding remainder, 7%3, you’ll get 1.

What’s more, if we add or subtract multiples of 3 to 7, the results will also have remainder 1. Here’s some examples:

• 1 = 0 * 3 + 1
• 4 = 1 * 3 + 1
• 7 = 2 * 3 + 1
• 10 = 3 * 3 + 1
• 13 = 3 * 4 + 1
• 16 = 3 * 5 + 1

Clearly, the numbers which have remainder 1 when divided by 3 are of the form k * 3 + 1, where k is any integer value.

Hmm, did I say “clearly”? Let’s check out some more examples:

• -2 = -1 * 3 + 1
• -5 = -2 * 3 + 1
• …

Looks good, doesn’t it? Now ask your programming language again. If you use Javascript or Java,

//Java, Javascript
-2%3 = -2

whereas Python returns the expected 1

#Python
-2%3 = 1

So what’s going on here?

The modulo operator % in Java and Javascript is based on the “truncated division”, that returns the integer part of the quotient. On the other hand, the operator % in Python is based on the “floored division”, that returns the largest integer less than or equal to the quotient.

Therefore, in Javascript and Java:

• -2 = 0 * 3 – 2
• -5 = -1 * 3 – 2
• …

It’s still possible to simulate the floored division in Java and Javascript by using specific methods:

//Javascript
Math.floor(-2/3) = -1
remainder = -2 - Math.floor(-2/3) * 3 = 1

//Java
Math.floorDiv(-2,3) = -1
remainder = Math.floorMod(-2,3) = 1

The remainder of the truncated division always has the same sign as the dividend whereas the remainder of the floored division has the same sign as the divisor. Check Wikipedia for more details.

Although both definitions are valid, floored division is preferred in number theory and is the base of modular arithmetic and modern cryptography.