Exercise 3.2.23* ($\sum_{i=1}^{\lfloor a/2 \rfloor} \lfloor ib/a \rfloor + \sum_{j=1}^{\lfloor b/2 \rfloor} \lfloor ja/b \rfloor = \lfloor a/2 \rfloor \lfloor b/2 \rfloor + \lfloor (a,b)/2\rfloor$)

Question

Show that if $a$ and $b$ are positive integers then 
$$\sum_{i=1}^{\lfloor a/2 \rfloor} \lfloor ib/a \rfloor + \sum_{j=1}^{\lfloor b/2 \rfloor} \lfloor ja/b \rfloor = \lfloor a/2 \rfloor \lfloor b/2 \rfloor + \lfloor (a,b)/2\rfloor$$

Richard Ganaye · Accepted Answer

\begin{proof} As in the proof of the law of quadratic reciprocity (p.138), consider the set $\mathscr{S}$ of all ordered pairs of integers $(x,y)$ satisfying $1 \leq x \leq a/2 $, $1 \leq y \leq b/2 $. These conditions are equivalent to $1 \leq x \leq \lfloor a/2floor  $, $1 \leq y \leq \lfloor b/2 floor $, so
$$\mathrm{Card}\ S = \left\lfloor \frac{a}{2} ight floor  \left\lfloor \frac{b}{2} ight floor .$$
Separate this set into three mutually exclusive subsets $\mathscr{S}_1, \mathscr{S}_2, \mathscr{D}$, where
\begin{align*}
\mathscr{S}_1 &= \{(x,y) \in \mathscr{S} \mid bx -ay >0\},\
\mathscr{S}_2 &= \{(x,y) \in \mathscr{S} \mid bx -ay <0\},\
\mathscr{D}&= \{(x,y) \in \mathscr{S} \mid bx -ay =0\}.
\end{align*}
If $L$ is the line with equation $bx - ay = 0$, then $ \mathrm{Card}\ \mathscr{S}_1$ is the number of points of $\mathscr{S}$ under the line $L$, $ \mathrm{Card}\ \mathscr{S}_2$ is the number of points of $\mathscr{S}$ above the line $L$, and $ \mathrm{Card}\ \mathscr{D}$ the number of points of $S$ on the line $L$.
Then
 \begin{align*}
\mathrm{Card}\ S &=  \mathrm{Card}\  \mathscr{S}_1 +  \mathrm{Card}\  \mathscr{S}_2 + \mathrm{Card}\  \mathscr D,
\end{align*}
thus
\begin{align}
\mathrm{Card}\ S &= \mathrm{Card} (\mathscr{S}_1 \cup \mathscr D) + \mathrm{Card} (\mathscr{S}_2 \cup \mathscr D) - \mathrm{Card}\  \mathscr D.
\end{align}
We compute separately this three terms.

\begin{itemize}
\item The set $\mathscr{S}_1 \cup \mathscr D$ can be described as the set of points $(x,y) \in \mathscr{S}$ under or on the line $L$, i.e. the points $(x,y)$ such that $1 \leq x \leq  a/2,\ 1 \leq y \leq bx/a$, or equivalently, $1 \leq x \leq \lfloor a/2 floor,\ 1 \leq y \leq \lfloor bx/a floor$. Therefore
$$\mathrm{Card} (\mathscr{S}_1 \cup \mathscr D) =\sum_{i=1}^{\lfloor a/2 floor} \left \lfloor \frac{ib}{a} ight floor.$$
\item Symmetrically, $\mathscr{S}_2$ consists of the ordered pairs $(x,y)$ such that $1 \leq y \leq \lfloor b/2 floor, \ 1 \leq x \leq \lfloor a y/b floor$, so
$$\mathrm{Card} (\mathscr{S}_2 \cup \mathscr D) =\sum_{j=1}^{\lfloor b/2 floor} \left \lfloor \frac{ja}{b} ight floor.$$
\item Let $(x,y) \in S$. Then $(x,y) \in \mathscr{D}$ if and only if $bx -a y = 0$. Put $d = a \wedge b = \mathrm{gcd}(a, b)$. Then
\begin{align*}
(x,y) \in \mathscr{D} & \iff bx - a y = 0\
&\iff \frac{b}{d} \, x - \frac{a}{d}\, y = 0.
\end{align*}
Since $\frac{b}{d} \wedge \frac{a}{d} = 1$, and $\frac{a}{d} \mid \frac{b}{d} \, x$, then $\frac{a}{d} \mid x$, where $1 \leq x \leq \frac{a}{2}$. Thus $x = \lambda (a/d) \leq a/2 $ for some integer $\lambda$, where $1 \leq \lambda \leq d/2$, and $y = \lambda (b/d)$.

Conversely every point $\left(\lambda \frac{a}{d}, \lambda \frac{b}{d}ight )$, where $1 \leq \lambda \leq d/2$ is in $\mathscr{D}$. Therefore $\mathscr{D}$ is the set of $(x,y) =\left(\lambda \frac{a}{d}, \lambda \frac{b}{d}ight )$ such that $1 \leq \lambda \leq \lfloor d/2 floor$, so
$$\mathrm{Card}\ \mathscr{D} = \left \lfloor \frac{a \wedge b}{2} ight floor.$$
\end{itemize}
Then equation (1) gives
$$\sum_{i=1}^{\lfloor a/2 floor} \left \lfloor \frac{ib}{a} ight floor + \sum_{j=1}^{\lfloor b/2 floor} \left \lfloor \frac{ja}{b} ight floor = \left\lfloor \frac{a}{2} ight floor  \left\lfloor \frac{b}{2} ight floor + \left \lfloor \frac{a \wedge b}{2} ight floor.$$
\end{proof}

Exercise 3.2.23* ($\sum_{i=1}^{\lfloor a/2 \rfloor} \lfloor ib/a \rfloor + \sum_{j=1}^{\lfloor b/2 \rfloor} \lfloor ja/b \rfloor = \lfloor a/2 \rfloor \lfloor b/2 \rfloor + \lfloor (a,b)/2\rfloor$)

Answers

Comments

Exercise 3.2.23* ($\sum_{i=1}^{\lfloor a/2 \rfloor} \lfloor ib/a \rfloor + \sum_{j=1}^{\lfloor b/2 \rfloor} \lfloor ja/b \rfloor = \lfloor a/2 \rfloor \lfloor b/2 \rfloor + \lfloor (a,b)/2\rfloor$)

Answers

Comments

Add answer