Prove that $ (n,m)=2 \sum\limits_{i=1}^{n-1} \left[ \frac{i m}{n}\right]+n+m - n m. $

Question

Prove that

$$ (n,m)=2 \sum_{i=1}^{n-1} \left[ \frac{i\, m}{n}\right]+n+m - n\, m. $$

Answer 1

Let's look first at the following sum : $$S=\sum_{i=1}^{n-1} \left[ \frac{i\,m}{n}\right]\implies S=\sum_{i=1}^{n-1} \left[ \frac{(n-i) m}{n}\right]$$ So we will have : $$\begin{align*} 2S &=\sum_{i=1}^{n-1}\left(\left[ \frac{i\,m}{n}\right]+\left[ \frac{(n-i) m}{n}\right]\right)\\ &=\sum_{i=1}^{n-1}\left(m+\left[ \frac{i\,m}{n}\right]+\left[ -\frac{i m}{n}\right]\right)\\ &=m(n-1)+\sum_{i=1}^{n-1}\left(\left[ \frac{i\,m}{n}\right]+\left[ -\frac{i m}{n}\right]\right)\end{align*}$$

But we know that: ${\displaystyle \left[ x\right] +\left[ -x\right] =0 \mbox{ if }}x\in \mathbb {Z}$ and $-1{\mbox{ if }}x\not \in \mathbb {Z} $,This terminates the proof by noticing that $\frac{i\,m}{n}$ is an integer iff $i$ is divisible by $\frac{n}{(n,m)}$ and there are exactly $(n,m)$ divisors of this number in the range $[1,n]$ : $$\sum_{i=1}^{n}\left(\left[ \frac{i\,m}{n}\right]+\left[ -\frac{i m}{n}\right]\right)=-n+\sum_{1\leq i\leq n,\frac{i\,m}{n}\in \mathbb{Z}}1=-n+(n,m)$$

Finally:

$$2\sum_{i=1}^{n-1} \left[ \frac{i\,m}{n}\right]=m(n-1)-n+(n,m) $$