Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can we evaluate the exact form of $$g\left(k,n\right)=\sum_{r=0}^{n-1}\exp\left(2\pi i\frac{r^{2}k}{n}\right) $$ for general $k$ and $n$? For $k=1$, on MathWorld we have that $$g\left(1,n\right)=\left\{ \begin{array}{cc} (1+i)\sqrt{n} & \ \text{when}\ n\equiv0\ \text{mod}\ 4\\ \sqrt{n} & \text{when}\ n\equiv1\ \text{mod}\ 4\\ 0 & \text{when}\ n\equiv2\ \text{mod}\ 4\\ i\sqrt{n} & \text{when}\ n\equiv3\ \text{mod}\ 4 \end{array}\right\} .$$

I know how to generalize to all $k$ when $n=p$ is a prime number, but what do we do when $n$ is not prime? Is there a simple way to rewrite it using whether or not $k$ is a square? I have a suspicion it should be fairly close to the form above, any help is appreciated.


share|cite|improve this question
up vote 5 down vote accepted

They do not provide a derivation, but this is actually written up in Wikipedia.

I use the standard notation $e(x) = \exp(2 \pi i x)$. Assuming $\gcd(k,n) = 1$, we have $$ \sum_{x \in \mathbb{Z}/n \mathbb{Z}} e\left(\frac{kx^2}{n} \right) = \left\{ \begin{array}{lcl} \varepsilon_n \left( \frac{k}{n} \right) \sqrt{n} & & n \equiv 1 \pmod{2}\\ 0 & & n \equiv 2\pmod{4}\\ (1 + i) \varepsilon_k^{-1} \left(\frac{n}{k} \right)\sqrt{n} & & k \equiv 1 \pmod{2}, 4 \mid n \end{array}\right. $$ where $\left( \cdot \right)$ and for odd $m$, $$ \varepsilon_m = \left\{ \begin{array}{cc} 1 & & m \equiv 1 \pmod{4}\\ i & & m \equiv 3 \pmod{4} \end{array}\right. $$ When $\gcd(k,n) > 1$, write $k' = k/\gcd(k,n)$ and $n' = n/\gcd(k,n)$, to see that $$ \sum_{x \in \mathbb{Z}/n \mathbb{Z}} e\left(\frac{kx^2}{n} \right)= \gcd(k,n) \sum_{x \in \mathbb{Z}/ n' \mathbb{Z}} e\left(\frac{k' x^2}{n'} \right) $$ since the variable $x$ runs through $\gcd(k,n)$ copies of the above sum.

Added: I looked through Iwaniec-Kowalski and they have a few notes on the sums, but nothing short worth noting here. These sums are discuss in Chapter 3 (around page 49) of their book. Anyways, I hope this answer is what you were looking for.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.