[proofplan] The [Gauss sum](/page/Gauss%20Sum) $\tau(\chi)$ is the finite sum $\sum_{r=1}^{q}\chi(r)e^{2\pi i r/q}$ appearing in the statement. We prove the identity by separating the frequency $n$ according to whether it is invertible modulo $q$. If $\gcd(n,q)=1$, multiplication by $n$ permutes the residue classes modulo $q$, and the Gauss sum transforms by the multiplicative factor determined by \begin{align*} \chi(n)^{-1}=\overline{\chi(n)}. \end{align*} If $\gcd(n,q)>1$, the additive character $r \mapsto e^{2\pi i n r/q}$ factors through a proper quotient of $\mathbb{Z}/q\mathbb{Z}$; primitivity of $\chi$ forces the sum of $\chi$ over every fibre of that quotient to vanish. Since $\chi(n)=0$ in the non-coprime case, this gives both sides equal to zero. [/proofplan]

[step:Dispose of the modulus $q=1$] If $q=1$, then the only [Dirichlet character](/page/Dirichlet%20Character) modulo $1$ is given by $\chi(m)=1$ for every $m \in \mathbb{Z}$. Hence \begin{align*} \sum_{r=1}^{1}\chi(r)e^{2\pi i n r} = e^{2\pi i n} = 1 = \overline{\chi(n)}\,\tau(\chi), \end{align*} because $n \in \mathbb{Z}$ and $\tau(\chi)=\chi(1)e^{2\pi i}=1$. Thus the identity holds for $q=1$. For the remainder of the proof, assume $q \geq 2$. [/step]

[step:Evaluate the Fourier coefficient when $n$ is invertible modulo $q$]Assume first that $\gcd(n,q)=1$. Let $\bar{n} \in \mathbb{Z}$ denote an inverse of $n$ modulo $q$, so that $n\bar{n}\equiv 1 \pmod q$. Multiplication by $n$ defines a permutation of the residue classes modulo $q$, so the substitution $s \equiv nr \pmod q$ changes the summation over $r=1,\dots,q$ into a summation over $s=1,\dots,q$. Since $r \equiv \bar{n}s \pmod q$ and $\chi$ is periodic modulo $q$ and multiplicative, we obtain \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} &= \sum_{s=1}^{q}\chi(\bar{n}s)e^{2\pi i s/q} \\ &= \chi(\bar{n})\sum_{s=1}^{q}\chi(s)e^{2\pi i s/q}. \end{align*} Because $\gcd(n,q)=1$, the value $\chi(n)$ is a root of unity. Since $\chi(n)\chi(\bar{n})=\chi(n\bar{n})=\chi(1)=1$, we have \begin{align*} \chi(\bar{n})=\chi(n)^{-1}=\overline{\chi(n)}. \end{align*} Therefore \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} = \overline{\chi(n)}\,\tau(\chi). \end{align*}[/step]

[guided]Assume that $n$ is invertible modulo $q$. The point is that the additive factor $e^{2\pi i n r/q}$ can be converted into the standard additive factor $e^{2\pi i s/q}$ by the change of residue class $s \equiv nr \pmod q$. Let $\bar{n} \in \mathbb{Z}$ be chosen so that $n\bar{n}\equiv 1 \pmod q$. Since $\gcd(n,q)=1$, multiplication by $n$ is a bijection on the residue classes modulo $q$. Therefore, as $r$ runs through a complete residue system $1,\dots,q$, so does $s\equiv nr\pmod q$. Under this substitution, $r\equiv \bar{n}s\pmod q$. Since $\chi$ depends only on the residue class modulo $q$, we have $\chi(r)=\chi(\bar{n}s)$. Hence \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} &= \sum_{s=1}^{q}\chi(\bar{n}s)e^{2\pi i s/q}. \end{align*} Now we use multiplicativity of the Dirichlet character. Because $\bar{n}$ is coprime to $q$, $\chi(\bar{n})\neq 0$, and for every integer $s$, \begin{align*} \chi(\bar{n}s)=\chi(\bar{n})\chi(s). \end{align*} Thus \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} &= \chi(\bar{n})\sum_{s=1}^{q}\chi(s)e^{2\pi i s/q}. \end{align*} The sum on the right is exactly the [Gauss sum](/page/Gauss%20Sum) $\tau(\chi)$ by its definition in the statement. Finally, since $\chi(n)$ is a root of unity for $\gcd(n,q)=1$, its inverse equals its complex conjugate. Also $\chi(n)\chi(\bar{n})=\chi(n\bar{n})=\chi(1)=1$, so \begin{align*} \chi(\bar{n})=\chi(n)^{-1}=\overline{\chi(n)}. \end{align*} Therefore \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} = \overline{\chi(n)}\,\tau(\chi). \end{align*}[/guided]

[step:Show that primitive characters have zero sums on proper quotient fibres]Let $Q$ be a proper positive divisor of $q$. For each residue class $a \in \mathbb{Z}/Q\mathbb{Z}$, define \begin{align*} S_a := \sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(r). \end{align*} We claim that $S_a=0$ for every $a \in \mathbb{Z}/Q\mathbb{Z}$. Let \begin{align*} \rho:(\mathbb{Z}/q\mathbb{Z})^\times &\to (\mathbb{Z}/Q\mathbb{Z})^\times \\ [r]_q &\mapsto [r]_Q \end{align*} denote the reduction homomorphism on unit groups. We first justify the primitive-character input. Suppose, toward a contradiction, that $\chi$ is trivial on $\ker \rho$. The reduction map $\rho$ is surjective because $Q$ divides $q$. To verify this, write $q=\prod_{p\mid q}p^{\alpha_p}$ and $Q=\prod_{p\mid q}p^{\beta_p}$, where $0\leq \beta_p\leq \alpha_p$. For a class $[a]_Q\in (\mathbb{Z}/Q\mathbb{Z})^\times$, impose the congruence $b\equiv a\pmod {p^{\beta_p}}$ when $\beta_p>0$ and impose $b\equiv 1\pmod {p^{\alpha_p}}$ when $\beta_p=0$. These congruences are imposed modulo pairwise coprime prime powers, so the [Chinese Remainder Theorem](/page/Chinese%20Remainder%20Theorem) gives an integer $b$ satisfying them simultaneously. Then $b\equiv a\pmod Q$, and $p\nmid b$ for every prime $p\mid q$, hence $\gcd(b,q)=1$. Define \begin{align*} \psi:(\mathbb{Z}/Q\mathbb{Z})^\times &\to \mathbb{C}^\times \\ \rho([r]_q) &\mapsto \chi(r). \end{align*} This map is well-defined: if $\rho([r]_q)=\rho([s]_q)$, then $[r]_q[s]_q^{-1}\in\ker\rho$, so triviality on $\ker\rho$ gives $\chi(r)\chi(s)^{-1}=1$. It is a group homomorphism because $\chi$ is multiplicative. Extending $\psi$ to all integers by setting $\psi(m)=0$ when $\gcd(m,Q)>1$ produces a Dirichlet character modulo $Q$ whose pullback to modulus $q$ agrees with $\chi$ on every integer coprime to $q$. Thus $\chi$ would be induced from the proper modulus $Q$, contradicting primitivity. Therefore $\chi|_{\ker\rho}$ is nontrivial, so there exists an integer $u$ such that $\gcd(u,q)=1$, $u\equiv 1\pmod Q$, and $\chi(u)\neq 1$. Multiplication by $u$ permutes the set of residues $r \pmod q$ satisfying $r\equiv a\pmod Q$, because $u$ is invertible modulo $q$ and $u\equiv 1\pmod Q$. Hence \begin{align*} S_a &= \sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(ur) \\ &= \chi(u)\sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(r) \\ &= \chi(u)S_a. \end{align*} Since $\chi(u)\neq 1$, this implies $S_a=0$.[/step]

[guided]We now prove the cancellation fact that uses primitivity. Let $Q$ be a proper divisor of $q$. We group residue classes modulo $q$ according to their image modulo $Q$. For a residue class $a \in \mathbb{Z}/Q\mathbb{Z}$, define \begin{align*} S_a := \sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(r). \end{align*} We want to prove $S_a=0$. Why should [primitivity](/page/Primitive%20Dirichlet%20Character) imply this cancellation? Let \begin{align*} \rho:(\mathbb{Z}/q\mathbb{Z})^\times &\to (\mathbb{Z}/Q\mathbb{Z})^\times \\ [r]_q &\mapsto [r]_Q \end{align*} be the reduction homomorphism. We need a unit $u$ modulo $q$ that lies in $\ker\rho$ but on which $\chi$ is not equal to $1$. Suppose no such unit existed. Then $\chi$ would be trivial on $\ker\rho$. We now show why that would contradict primitivity. Since $Q$ divides $q$, the reduction map $\rho$ is surjective. Write $q=\prod_{p\mid q}p^{\alpha_p}$ and $Q=\prod_{p\mid q}p^{\beta_p}$, with $0\leq \beta_p\leq \alpha_p$. Given a unit class $[a]_Q\in (\mathbb{Z}/Q\mathbb{Z})^\times$, require $b\equiv a\pmod {p^{\beta_p}}$ for each prime $p$ with $\beta_p>0$, and require $b\equiv 1\pmod {p^{\alpha_p}}$ for each prime $p$ with $\beta_p=0$. The moduli involved are pairwise coprime, so the [Chinese Remainder Theorem](/page/Chinese%20Remainder%20Theorem) produces an integer $b$ satisfying all these congruences. This integer satisfies $b\equiv a\pmod Q$, and it is not divisible by any prime dividing $q$, so $\gcd(b,q)=1$. Thus $\rho$ is surjective. Hence, if $\chi$ is trivial on $\ker\rho$, we may define \begin{align*} \psi:(\mathbb{Z}/Q\mathbb{Z})^\times &\to \mathbb{C}^\times \\ \rho([r]_q) &\mapsto \chi(r). \end{align*} This definition is independent of the chosen lift $[r]_q$: if two lifts $[r]_q$ and $[s]_q$ have the same image modulo $Q$, then $[r]_q[s]_q^{-1}\in\ker\rho$, and triviality on $\ker\rho$ gives $\chi(r)=\chi(s)$. The map $\psi$ is multiplicative because $\chi$ is multiplicative. Extending $\psi$ to all integers by the Dirichlet-character convention $\psi(m)=0$ when $\gcd(m,Q)>1$ gives a character modulo $Q$ inducing $\chi$ on the unit classes modulo $q$. This contradicts the assumption that $\chi$ is primitive modulo $q$. Therefore there exists an integer $u$ such that \begin{align*} \gcd(u,q)=1,\qquad u\equiv 1\pmod Q,\qquad \chi(u)\neq 1. \end{align*} Now consider multiplication by this $u$. Since $\gcd(u,q)=1$, multiplication by $u$ is a permutation of the residue classes modulo $q$. Since $u\equiv 1\pmod Q$, it preserves each fibre over modulo $Q$: if $r\equiv a\pmod Q$, then $ur\equiv r\equiv a\pmod Q$. Therefore multiplication by $u$ permutes the finite set of residues modulo $q$ satisfying $r\equiv a\pmod Q$. Using this permutation in the sum defining $S_a$, we get \begin{align*} S_a &= \sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(ur). \end{align*} By multiplicativity of the Dirichlet character, \begin{align*} \chi(ur)=\chi(u)\chi(r) \end{align*} for every integer $r$. Hence \begin{align*} S_a &= \chi(u)\sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(r) \\ &= \chi(u)S_a. \end{align*} Since $\chi(u)\neq 1$, subtracting $\chi(u)S_a$ from both sides gives \begin{align*} (1-\chi(u))S_a=0, \end{align*} and therefore $S_a=0$.[/guided]

[step:Use fibre cancellation when $n$ is not invertible modulo $q$]Assume now that $\gcd(n,q)>1$. Let $d:=\gcd(n,q)$ and define $Q:=q/d$. Then $Q$ is a proper positive divisor of $q$. The additive factor \begin{align*} r \mapsto e^{2\pi i n r/q} \end{align*} depends only on the residue class of $r$ modulo $Q$, because $n/q=(n/d)/Q$. Therefore, grouping the sum according to residue classes $a \in \mathbb{Z}/Q\mathbb{Z}$, we obtain \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} &= \sum_{a \in \mathbb{Z}/Q\mathbb{Z}} e^{2\pi i n a/q} \sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(r). \end{align*} By the fibre cancellation proved in the previous step, each inner sum is zero. Hence \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q}=0. \end{align*} Since $\gcd(n,q)>1$, the Dirichlet character satisfies $\chi(n)=0$, so \begin{align*} \overline{\chi(n)}\,\tau(\chi)=0. \end{align*} Thus the desired identity also holds in the non-coprime case.[/step]

[guided]Now assume that $n$ is not invertible modulo $q$. Let \begin{align*} d:=\gcd(n,q), \qquad Q:=q/d. \end{align*} Since $d>1$, $Q$ is a proper positive divisor of $q$. The additive character has become less oscillatory than a primitive additive character modulo $q$. Indeed, \begin{align*} \frac{n}{q}=\frac{n/d}{q/d}=\frac{n/d}{Q}, \end{align*} so $e^{2\pi i n r/q}$ depends only on $r$ modulo $Q$. Thus, if $r\equiv a\pmod Q$, then \begin{align*} e^{2\pi i n r/q}=e^{2\pi i n a/q}. \end{align*} We group the original sum by fibres of the reduction map modulo $Q$: \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} &= \sum_{a \in \mathbb{Z}/Q\mathbb{Z}} e^{2\pi i n a/q} \sum_{\substack{1\leq r\leq q \\ r\equiv a \!\!\!\pmod Q}} \chi(r). \end{align*} The inner sum is exactly the fibre sum $S_a$ from the previous step. Because $\chi$ is primitive modulo $q$ and $Q$ is a proper divisor of $q$, that step gives $S_a=0$ for every $a \in \mathbb{Z}/Q\mathbb{Z}$. Therefore every term in the outer sum is zero, and hence \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q}=0. \end{align*} Finally, since $\gcd(n,q)>1$, the defining extension of a Dirichlet character to all integers gives $\chi(n)=0$. Therefore \begin{align*} \overline{\chi(n)}\,\tau(\chi)=0. \end{align*} Both sides are zero, so the identity holds in this case.[/guided]

[step:Combine the coprime and non-coprime cases]For every integer $n$, either $\gcd(n,q)=1$ or $\gcd(n,q)>1$. The invertible case gives \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} = \overline{\chi(n)}\,\tau(\chi), \end{align*} and the non-invertible case gives the same identity with both sides equal to zero. Therefore the stated formula holds for every $n\in\mathbb{Z}$.[/step]

[guided]It remains only to assemble the two mutually exclusive cases. Fix an integer $n\in\mathbb{Z}$. If $\gcd(n,q)=1$, the invertible-case step proved directly that \begin{align*} \sum_{r=1}^{q}\chi(r)e^{2\pi i n r/q} = \overline{\chi(n)}\,\tau(\chi). \end{align*} If instead $\gcd(n,q)>1$, the fibre-cancellation step proved that the left-hand side is zero, and the defining extension of a Dirichlet character to non-units gives $\chi(n)=0$, so \begin{align*} \overline{\chi(n)}\,\tau(\chi)=0. \end{align*} Thus the same displayed identity holds in both cases. Since every integer $n$ belongs to exactly one of these two cases, the formula holds for every $n\in\mathbb{Z}$.[/guided]