Prove that $ (n,m)=2 \sum\limits_{i=1}^{n-1} \left[ \frac{i m}{n}\right]+n+m - n m. $ Prove  that
$$
(n,m)=2 \sum_{i=1}^{n-1} \left[ \frac{i\,  m}{n}\right]+n+m - n\,  m.
$$
 A: 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) $$

