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
    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?2011-11-20
  • 3
    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))$.2011-11-20
  • 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 be n.2011-11-20