Exercise 4.1.18* (Prove $\sum_{x=1}^{n-1} \left \lfloor \frac{mx}{n} \right \rfloor = \frac{(m-1)(n-1)}{2}$ if $(m,n)=1$)

Proof. As in the proof of quadratic reciprocity, consider the set

and

( $A$ and $B$ are the sets of points in $E$ respectively under the line $D$ and above the line $D$, whose equation is $\mathit{nx}+\mathit{my}=0$. Draw a figure for some fixed values of $m$ and $n$.)

We note first that no point $(i,j)\in E$ satisfies $\mathit{ni}=\mathit{mj}$, otherwise $n\mid \mathit{mj}$, where $n\wedge m=1$, thus $n\mid j$. Since $1\le j<n$, this is impossible. This prove that $B$ is the complementary set of $A$ in $E$, so that

Moreover, because of the symmetry of the figure about the point $(m∕2,n∕2)$, there are as many points in $E$ under the line $D$ than above. More formally, consider the maps

This makes sense, because

and similarly $(i,j)\in B\Rightarrow (m-i,n-i)\in A$.

Moreover $\psi \circ \phi =1_A,\phi \circ \psi =1_B$, therefore $\phi$ is a bijection, and $\psi ={\phi }^{-1}$. This proves that $|A|=|B|$, thus

For a fixed $i_0\in [[1,m-1]]$, consider the set

Then

Therefore $|A|={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^{m-1}|A_i|$, where

Thus

In conclusion, if $m\wedge n=1$, then

□