Two kinds of remainders

Intro

I was messing around with my haskell CLI, when I noticed there are actually two different functions that give you the remainder of an integer division:

Prelude> 27 `mod` 4
3
Prelude> 27 `rem` 4
3

Okay, so why did they bother implementing the same function twice, if they just give you the same answer?

Well, as it turns out, they don’t. They show different behaviors with negative numbers:

Prelude> 27 `mod` (-4)
-1
Prelude> 27 `rem` (-4)
3

To understand the difference, and why these two versions might be useful, let’s rebuild our understanding from the very basics of division:

Euclidean division

This is how euclidean division is defined:

Given two integers a and b, with b ≠ 0,
there exist unique integers q and r such that
a = bq + r and 0 ≤ r < |b|.

That’s a ÷ b.

This theorem tells us about the existence of two numbers, the quotient and the remainder. Whatever dividend a and divisor b you start with, you can always find two numbers q and r —the quotient and the remainder— that satisfy both conditions. Moreover, they are unique.

Actually, if you don’t care about 0 ≤ r < |b|, there are lots of different q and r to choose from, (actually infinitely many of them).

Let’s take 14 ÷ 3 for example. You could write:

• 14 = 3 × 3 + 5
• 14 = 3 × 4 + 2
• 14 = 3 × 5 − 1
• 14 = 3 × 6 − 4

Each equality is true, and you could extend this list in both directions indefinitely. But the only equality that really tells us something meaningful is the one that verifies 0 ≤ r < |3|:

• 14 = 3 × 4 + 2

It tells us that, when you have 14 items, you can make 4 chunks of 3 items. You cannot make more than that, as there is not enough items left over.

If you have 14 matches, you can make 4 distinct triangles, but not 5. There is not enough matches left to make another one.

Dividing a by b, fundamentally means looking how many times b can fit into a; how many chunks of b things you can make out of a things; how many stacks of b apples you can make out of a apples.

Finding the answer comes down to this: Keep subtracting b from a until you can’t subtract any more.

You can remove 4 chunks of 3 from 14, but not 5. You could still take 2 to go to 0, but you can’t remove one complete chunk of 3.

So, what happens with negative numbers?

There is no really obvious way to do the same thing with negative numbers. What does it even mean to divide by a negative number? Or divide a negative number?

The usual way to proceed in maths is by extrapolation. We try to apply the same process in the new domain as in the previous domain (where we know it works), in a way that makes sense and that doesn’t blow up in our face.

Simple case

First, let’s try −14 ÷ (−3)

How many times does −3 go into −14? We can’t really visualize stacks of −3 things.

But we can try to replicate what we were doing when we were subtracting 3 from 14. So, let’s try subtracting −3 from −14.
After all, −3 and −14 are of the same kind, they are made of the same material, “negative stuff”.
Removing negative stuff, is like adding positive stuff. We get “less negative”.

It works. We can keep subtracting until there is not enough left, and we get −2 as remainder.

So once gain, it’s 4 times. We can make 4 chunks of −3 things out of −14 things.

You can visualise 4 chunks made of 3 (−1)’s, and a remainder of 2 (−1)’s.

Let’s write the thing again:

−14 = −3 × 4 − 2

Did you notice something? This remainder doesn’t abide by our definition. We saw ealier that the remainder must verify:

0 ≤ r < |b|

r is supposed to be positive!

To get our positive remainder, we need to go one step further. let’s subtract −3 once more!

The equality becomes:

−14 = −3 × 5 + 1

This time, we are making 5 stacks of −3. But we have subtracted too much. We need to add some back so that we have the initial count of −14, making the remainder +1.

The intuition is a bit left behind. We can’t really relate with our real world experience of division as making smaller chunks out of a bigger chunk. But that’s just how the euclidean division is defined.

But as you’ll see, this gets even weirder.

Before we look at the next example, let’s check what haskell is doing:

Prelude> (-14) `rem` (-3)
-2
Prelude> (-14) `mod` (-3)
-2

Neither seems to be returning a positive remainder. But at least, so far they give us the same answer.

In JavaScript, % gives us the same answer as well:

> -14 % -3
-2

less simple case

Now, what if we want to do −14 ÷ 3 ?

So, how many times 3 goes into −14? This time −14 and 3 are not even made of the same material: one is negative, the other positive. How would you make stacks of 3 objects out of −14 objects?

You could keep subtracting stacks of 3, as we did previously, but you’d be going in the wrong direction indefinitely.

To find something equivalent that makes some sort of sense, the idea is to keep adding 3’s —and not subtracting— until you can’t keep adding anymore.

This case is actually pretty similar to the previous one. Adding 3 is the same as subtracting −3.

You could also think of this as cutting −14 into 3 equal parts, and see what remains, but let’s keep following our initial idea all the way.

Remember, in 14 ÷ 3, we were making 4 stacks of 3 elements, and to find the remainder, we were removing one stack of 3 at a time until there wasn’t enough left to keep removing. When we are removing stacks from the dividend a, it means a positive number of stacks, in that case it was 4 stacks.

This time we are adding stacks to the dividend a. That must mean… a negative number of stacks!

So, we have −4 stacks of 3’s, plus a remainder of −2.

−14 = 3 × −4 − 2

Once again, we need to do a bit different to comply with the euclidean division definition:

−14 = 3 × −5 + 1

Let’s look at what haskell is doing this time:

Prelude> (-14) `rem` 3
-2
Prelude> (-14) `mod` 3
1

The two functions do not agree. rem seems to follow our intuitive approach (removing just enough), while mod follows the euclidean division definition.

If you’re curious, in JavaScript % is actually acting like rem.

> -14 % 3
-2

Last case

14 ÷ (−3).

In −14 ÷ (−3), we have already encountered the species of stacks of −3 things. But would that fit into a positive number of things?

Once again, we need to keep adding stacks, instead of removing. (Remember, subtracting means positive number of stacks, adding means negative number of stacks).

This is similar to our previous example, exept we are dealing with stacks of −3. We are adding stacks of −3. That means a negative number of stacks of a nagative number of things.

In the end, 14 is made of −4 stacks of −3, and a remainder of 2.

14 = −3 × −4 + 2

This time, we have a positive remainder right away.

Prelude> 14 `rem` (-3)
2
Prelude> 14 `mod` (-3)
-1

> -14 % 3
-2

Equivalence relations

To go further, I need to introduce the notion of equivalence relations. But first:

Binary relations

We say that an integer n is related to an integer m if they satisfy a given condition. We write n ~ m, for the ~ relation.

For example, we can say that n ~ m if n + m = 2.

(n and m are integer here, but you can have a binary relation on any kind of set).

An equivalence relation ~ is a binary relation that verifies:

• a ~ a (reflexivity)
• if a ~ b then b ~ a, (symmetry)
• if a ~ b and b ~ c then a ~ c (transivity)

Each condition must be verified for any a, b, c we choose.

For example, we can easily verify that the previous binary relation is not an equivalence relation:

5 + 5 ≠ 2, so 5 is not related with itself, so the relation is not reflexive.

Equality between two integers a and b is an equivalence relation:

• a = a, for all integer a.
• if a = b then b = a, for all a and b.
• if a = b and b = c then a = c, for all a, b and c

Having the same remainder when divided by an integer n also defines an equivalence relation. In maths, this relation has a special name: the congruence relation.

If two integers a and b have the same remainder in the division by n, we say that they are congruent modulo n, written:

a ≡ b mod n

For example,

• 14 = 10 × 1 + 4
• 24 = 10 × 2 + 4
• 34 = 10 × 3 + 4

14, 24, 34 are all congruent modulo 10. They all have the same remainder, 4.

Finding another number that is congruent modulo n is easy, you just have to add n. (That makes sense, we saw that dividing by n means keep removing stacks of n. Adding n doesn’t change the remainder when dividing by n).

Equivalence classes

If you take all the integers that have a remainder of 4 in the division by 10, you get what we called an equivalence class. That’s a way of saying “under this congruence relation, all these numbers are behaving the same. We won’t bother about each of them, we’ll just group them in one single object.”

In modular arithmetic, we consider that 4, 14, 104, 100000004 is just the same thing modulo 10.
We just choose one representative, 4, to represent them all.

Back to business

We have seen, in our previous meandering, that there is two main ways to deal with negative integer divisions:

• Either we choose to stop subtracting (or adding) groups of b elements from our a before we reach zero (the more intuitive approach)
• Or we choose to subtract (or add) one more group, so that we end up with a positive remainder.

Notice that we only have to worry about this if a is negative, which makes the remainder initially negative. In 14 ÷ (−3), we already end up with a positive remainder.

That makes sense. We start with a number a of things, we take some of it, and some is left over. It seems logical that the remainder should have the same sign as the dividend a.

What’s more important to notice is that, in both ways of doing negative integer divisions, the remainders will belong to the same equivalence class.

Whether you choose to do −14 = −3 × 4 − 2 or −14 = −3 × 5 + 1, having a remainder or −2, or 1 is really just the same thing. −2 and 1 belong to the same equivalence class modulo 3. That’s just a way to represent the same thing.

In arithmetic, we choose to have all our remainders to be positive. That way we automatically end up with the most natural representative of the equivalence class.

For example, modulo 3, we have 3 classes, 0, 1, 2.

This shows clearly when we look at successive divisions. The remainders keep cycling through 0, 1 and 2, repeating the same pattern.

• 1 = 3 × 0 + 1
• 2 = 3 × 0 + 2
• 3 = 3 × 1
• 4 = 3 × 1 + 1
• 5 = 3 × 1 + 2
• 6 = 3 × 2
• 7 = 3 × 2 + 1
• 8 = 3 × 2 + 2
• 9 = 3 × 3

Using rem, that nice pattern doesn’t continue toward the negative side, as rem will always be the same sign as the dividend a.

Prelude> map (`rem` 3) [-5..5]
[-2,-1,0,-2,-1,0,1,2,0,1,2]

• −5 = 3 × −1 − 2
• −4 = 3 × −1 − 1
• −3 = 3 × −1
• −2 = 3 × 0 − 2
• −1 = 3 × 0 − 1
• 0 = 3 × 0
• 1 = 3 × 0 + 1
• 2 = 3 × 0 + 2
• 3 = 3 × 1
• 4 = 3 × 1 + 1
• 5 = 3 × 1 + 2

Using mod, however, that nice pattern will be preserved:

Prelude> map (`mod` 3) [-5..5]
[1,2,0,1,2,0,1,2,0,1,2]

• −5 = 3 × −2 + 1
• −4 = 3 × −2 + 2
• −3 = 3 × −1
• −2 = 3 × −1 + 1
• −1 = 3 × −1 + 2
• 0 = 3 × 0
• 1 = 3 × 0 + 1
• 2 = 3 × 0 + 2
• 3 = 3 × 1
• 4 = 3 × 1 + 1
• 5 = 3 × 1 + 2

Summarizing

rem and mod will give the same answer if a and b have the same sign. If a and b have different signs, rem and mod will differ by b.

rem

rem corresponds to a more intuitive vision of doing integer divisions. In 14, there are 4 stacks of 3’s, no more.

The corresponding quotient will get trunkated toward zero. In haskell, that’s the function quot (the function quotRem will return both).

• 14 = 3 × 4 + 2
• 14 = −3 × (−4) + 2
• −14 = 3 × (−4) − 2
• −14 = (−3) × 4 − 2

Prelude> 14 `rem` 3
2
Prelude> 14 `rem` (-3)
2
Prelude> (-14) `rem` 3
-2
Prelude> (-14) `rem` (-3)
-2

> 14 % 3
2
> (-14) % (-3)
-2
> (-14) % 3
-2
> 14 % (-3)
2

However, rem won’t preserve the more natural representative of the equivalence classes.

mod

mod breaks intuition (when a and b have opposite signs), as it seems to be adding or subtracting one more than what’s really needed. It will keep the remainder the same sign as the divisor b.

The corresponding quotient will get trunkated toward negative infinity. In haskell, that’s the div function (the function divMod will return both).

• 14 = 3 × 4 + 2
• 14 = −3 × (−5) −1
• −14 = 3 × (−5) + 1
• −14 = (−3) × 4 − 2

Prelude> 14 `mod` 3
2
Prelude> 14 `mod` (-3)
-1
Prelude> (-14) `mod` 3
1
Prelude> (-14) `mod` (-3)
-2