An Identity about the fractional part

$$\sum_{j=1}^{n}\left(\left(\frac{jk}{n}\right)\right)=\frac{n-1}{2}$$ if $(n,k)=1$.

How could we show this identity?

-
Is $\left(\frac{jk}{n}\right)$ supposed to be a fraction or Legendre symbol or what? If it's a fraction, you'll need to edit the equation a bit in order to make it true. And what's with the double parentheses? – jwodder Nov 20 '11 at 19:36
I assume that $((x))=x-\lfloor x\rfloor$, the fractional part of $x$, but there’s still something wrong; it should probably be $\sum_{j=1}^n((jk/n))$. – Brian M. Scott Nov 20 '11 at 19:40
Just to confirm ; since it has been proved that $$\sum_{j=1}^n \left( \left( \frac{jk}{n} \right) \right) = \frac{n-1}2, \qquad \Longrightarrow \quad \sum_{j=1}^k \left( \left( \frac{jk}{n} \right) \right) < \frac{n-1}2.$$ unless $k=n-1$, because then $\sum_{j=1}^{n-1} = \sum_{j=1}^n$ since the last term doesn't contribute. – Patrick Da Silva Nov 20 '11 at 20:38

I’m assuming that the upper limit of the summation should be $n$; with $k$ there the result is false.
For $j=1,\dots,n$ write $jk=a_jn+r_j$, where $a_j$ and $r_j$ are integers and $0\le r_j<n$. If $(k,n)=1$, the integers $jk$ for $j=1,\dots,n$ are a complete residue system modulo $n$. Thus, they are congruent modulo $n$ to some permutation of $0,\dots,n-1$, and therefore $$\{r_j:j=1,\dots,n\}=\{0,\dots,n-1\}\;.$$ It follows immediately that $$\sum_{j=1}^n \left(\left(\frac{jk}n\right)\right) = \sum_{j=0}^{n-1}\frac{j}n = \frac{n-1}2\;.$$