TAOCP 1.2.4 Exercise 37

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 37. ▶ [M30] Let $m$ and $n$ be integers, $n>0$. Show that

$$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \frac{(m-1)(n-1)}{2} + \frac{d-1}{2} + d\left\lfloor \frac{x}{d} \right\rfloor, $$

where $d$ is the greatest common divisor of $m$ and $n$, and $x$ is any real number.

Verified: yes
Solve time: 11m54s

---

Let

$$ S(x)=\sum_{k=0}^{n-1}\left\lfloor \frac{mk+x}{n}\right\rfloor, $$

where $m,n\in\mathbb Z$, $n>0$, and let

$$ d=\gcd(m,n). $$

Write

$$ m=dm',\qquad n=dn', $$

with $\gcd(m',n')=1$.

We will prove that

$$ S(x)=\frac{(m-1)(n-1)}2+\frac{d-1}2+d\left\lfloor\frac{x}{d}\right\rfloor . $$

1. Decompose the index

Every $k$ with $0\le k<n=dn'$ can be written uniquely as

$$ k=qn'+r, \qquad 0\le q<d, \qquad 0\le r<n'. $$

Hence

$$ S(x) = \sum_{q=0}^{d-1}\sum_{r=0}^{n'-1} \left\lfloor \frac{dm'(qn'+r)+x}{dn'} \right\rfloor . $$

Since

$$ \frac{dm'(qn'+r)+x}{dn'} = m'q+\frac{dm'r+x}{dn'}, $$

and $m'q$ is an integer,

$$ \left\lfloor \frac{dm'(qn'+r)+x}{dn'} \right\rfloor = m'q+ \left\lfloor \frac{dm'r+x}{dn'} \right\rfloor . $$

Therefore

$$ S(x) = \sum_{q=0}^{d-1}\sum_{r=0}^{n'-1}m'q + d\sum_{r=0}^{n'-1} \left\lfloor \frac{m'r+x/d}{n'} \right\rfloor . $$

The first double sum equals

$$ n'm'\sum_{q=0}^{d-1}q = n'm'\frac{d(d-1)}2. $$

Thus

$$ S(x) = n'm'\frac{d(d-1)}2 + d\sum_{r=0}^{n'-1} \left\lfloor \frac{m'r+y}{n'} \right\rfloor , \tag{1} $$

where

$$ y=\frac{x}{d}. $$

2. Reduce to a coprime floor sum

For each $r$,

$$ m'r=n' t_r+s_r, \qquad 0\le s_r<n'. $$

Since $\gcd(m',n')=1$, the residues $s_r$ are exactly

$$ 0,1,\ldots,n'-1 $$

in some order.

Hence

$$ \left\lfloor \frac{m'r+y}{n'} \right\rfloor = t_r+ \left\lfloor \frac{s_r+y}{n'} \right\rfloor , $$

and therefore

$$ \sum_{r=0}^{n'-1} \left\lfloor \frac{m'r+y}{n'} \right\rfloor = \sum_{r=0}^{n'-1} t_r + \sum_{s=0}^{n'-1} \left\lfloor \frac{s+y}{n'} \right\rfloor . \tag{2} $$

To evaluate $\sum t_r$, sum the identities $m'r=n't_r+s_r$:

$$ m'\sum_{r=0}^{n'-1}r = n'\sum_{r=0}^{n'-1}t_r + \sum_{s=0}^{n'-1}s. $$

Since

$$ \sum_{r=0}^{n'-1}r = \sum_{s=0}^{n'-1}s = \frac{n'(n'-1)}2, $$

we obtain

$$ n'\sum_{r=0}^{n'-1}t_r = (m'-1)\frac{n'(n'-1)}2. $$

Hence

$$ \sum_{r=0}^{n'-1}t_r = \frac{(m'-1)(n'-1)}2. \tag{3} $$

3. Evaluate the auxiliary sum

Define

$$ A(y)= \sum_{s=0}^{n'-1} \left\lfloor \frac{s+y}{n'} \right\rfloor . $$

Write

$$ y=an'+b+\theta, $$

where

$$ a\in\mathbb Z,\qquad 0\le b<n',\qquad 0\le\theta<1. $$

Then

$$ \left\lfloor\frac{s+y}{n'}\right\rfloor = a+ \left\lfloor \frac{s+b+\theta}{n'} \right\rfloor . $$

Since $0\le s+b+\theta<2n'$, the second floor is either $0$ or $1$.

If $\theta=0$, it equals $1$ exactly when

$$ s\ge n'-b. $$

There are exactly $b$ such values of $s$, so

$$ A(y)=an'+b=\lfloor y\rfloor . $$

If $0<\theta<1$, then

$$ s+b+\theta\ge n' $$

is equivalent, for integral $s$, to

$$ s\ge n'-b. $$

Again there are exactly $b$ such values of $s$, giving

$$ A(y)=an'+b=\lfloor y\rfloor . $$

Therefore

$$ \sum_{s=0}^{n'-1} \left\lfloor \frac{s+y}{n'} \right\rfloor = \lfloor y\rfloor . \tag{4} $$

4. Substitute back

Combining (2), (3), and (4),

$$ \sum_{r=0}^{n'-1} \left\lfloor \frac{m'r+y}{n'} \right\rfloor = \frac{(m'-1)(n'-1)}2 + \lfloor y\rfloor . $$

Substituting into (1),

$$ S(x) = n'm'\frac{d(d-1)}2 + d\frac{(m'-1)(n'-1)}2 + d\left\lfloor\frac{x}{d}\right\rfloor . \tag{5} $$

Now simplify the constant term correctly. Using $m=dm'$ and $n=dn'$,

$$ n'm'\frac{d(d-1)}2 = \frac{mn-mn'}2, $$

and

$$ d\frac{(m'-1)(n'-1)}2 = \frac{dm'n'-dm'-dn'+d}{2} = \frac{mn-m-n+d}{2}. $$

Adding these gives

$$ \frac{mn-mn'}2+\frac{mn-m-n+d}{2}. $$

Since $n=dn'$,

$$ mn'=m\frac{n}{d}, $$

so

$$ \begin{aligned} &\frac{mn-mn'}2+\frac{mn-m-n+d}{2} \[1ex] &= \frac{2mn-mn'-m-n+d}{2}. \end{aligned} $$

Replacing $m=dm'$ and $n=dn'$,

$$ 2mn-mn' = 2d^2m'n'-dm'n' = d(2d-1)m'n'. $$

Hence the numerator becomes

$$ d(2d-1)m'n'-dm'-dn'+d. $$

On the other hand,

$$ (m-1)(n-1)+(d-1) = (dm'-1)(dn'-1)+d-1, $$

which expands to

$$ d^2m'n'-dm'-dn'+d. $$

Therefore it is better to simplify (5) directly in terms of $m'$ and $n'$:

$$ \begin{aligned} &n'm'\frac{d(d-1)}2 +d\frac{(m'-1)(n'-1)}2 \[1ex] &= \frac{d(d-1)m'n'+d(m'n'-m'-n'+1)}2 \[1ex] &= \frac{d^2m'n'-dm'-dn'+d}{2}. \end{aligned} $$

Since $m=dm'$ and $n=dn'$,

$$ \frac{d^2m'n'-dm'-dn'+d}{2} = \frac{mn-m-n+d}{2}. $$

Finally,

$$ \frac{mn-m-n+d}{2} = \frac{(m-1)(n-1)}2+\frac{d-1}{2}, $$

because

$$ (m-1)(n-1)+(d-1) = mn-m-n+d. $$

Substituting this into (5) yields

$$ S(x) = \frac{(m-1)(n-1)}2 + \frac{d-1}2 + d\left\lfloor\frac{x}{d}\right\rfloor . $$

Hence

$$ \boxed{ \sum_{0\le k<n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \frac{(m-1)(n-1)}2 + \frac{d-1}2 + d\left\lfloor\frac{x}{d}\right\rfloor }, $$

where $d=\gcd(m,n)$.

$\square$