Some identities involving integer division

I have worked out quite some identities involving integer division while writing other articles, and I decided to write them down for reference.

The variables $m$ , $n$ , $d$ are assumed to be integers (with $d \neq = 0$ ) throughout this article, whereas $x$ is a real variable.

Rounding up and down

When we divide unsigned integers n and d, the result gets rounded down. That is, n / d evaluates to $⌊ \frac{n}{d} ⌋$ . If we want to round up the quotient, we can do it as (n + d - 1) / d. Here, we are using the following identity:

⌊ \frac{n + d - 1}{d} ⌋ = ⌈ \frac{n}{d} ⌉

The relation between the floor and the ceil function is that

⌊ - x ⌋ = - ⌈ x ⌉

Rounding to multiples of $d$

To round down an integer $n$ to the nearest multiple of $d$ , we can use the expression $d ⌊ \frac{n}{d} ⌋$ . Alternatively, we can use modular arithmetic to write this expression as

n - mod_{d} (n)

Likewise, we can round up an integer $n$ to the nearest multiple of $d$ with the expression $d ⌈ \frac{n}{d} ⌉$ . With modular arithmetic we can write this as

n + mod_{d} (- n)

Getting rid of floor/ceil

Sometimes, it is useful to get rid of the floor or ceiling function from an expression. From the results in the last section we can derive the following identities which allow you to do this.

For the floor function, we have:

⌊ \frac{n}{d} ⌋ = \frac{n - mod _{d} ( n )}{d}

And for the ceil function:

⌈ \frac{n}{d} ⌉ = \frac{n + mod _{d} ( - n )}{d}

Sum identity

I write $q_{n} = ⌊ \frac{n}{d} ⌋$ , $p_{n} = mod_{d} (n)$ , so that we have $n = d q_{n} + p_{n}$ .

By working out $⌊ \frac{m + n}{d} ⌋ = ⌊ \frac{( d q _{m} + p _{m} ) + ( d q _{n} + p _{n} )}{d} ⌋$ we can prove that

q_{n + m} = q_{n} + q_{m} + ⌊ \frac{p _{n} + p _{m}}{d} ⌋

Likewise, we can write $s_{n} = ⌈ \frac{n}{d} ⌉$ , $r_{n} = mod_{d} (- n)$ , so that $n = d s_{n} - r_{- n}$ .

Then, we can work out $⌈ \frac{m + n}{d} ⌉ = ⌈ \frac{( d s _{m} - r _{m} ) + ( d s _{n} - r _{n} )}{d} ⌉$ and get the identity

s_{n + m} = s_{n} + s_{m} - ⌊ \frac{r _{n} + r _{m}}{d} ⌋

Product identity

Again, I write $q_{n} = ⌊ \frac{n}{d} ⌋$ , $p_{n} = mod_{d} (n)$ , so that we have $n = d q_{n} + p_{n}$ .

By working out and simplifying the expression $⌊ \frac{mn}{d} ⌋ = ⌊ \frac{( d q _{m} + p _{m} ) ( d q _{n} + p _{n} )}{d} ⌋$ we can prove that

q_{nm} = d q_{m} q_{n} + p_{m} q_{n} + q_{m} p_{n} + ⌊ \frac{p _{n} p _{m}}{d} ⌋

Again writing $s_{n} = ⌈ \frac{n}{d} ⌉$ , $r_{n} = mod_{d} (- n)$ , we have $n = d s_{n} - r_{- n}$ .

Now we can work out $⌈ \frac{mn}{d} ⌉ = ⌈ \frac{( d s _{m} + r _{m} ) ( d s _{n} + r _{n} )}{d} ⌉$ and get the identity