2
$\begingroup$

$\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?

  • 0
    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. – 2011-11-20

1 Answers 1

6

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. 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\;.$

  • 0
    Yes, it should $b$e n. – 2011-11-20