[proofplan] We compute the finite [Fourier transform](/page/Fourier%20Transform) of the primitive Dirichlet character $\chi$ on the residue classes modulo $q$. Let $\overline{\chi}: \mathbb{Z} \to \mathbb{C}$ denote the conjugate character defined by $\overline{\chi}(n)=\overline{\chi(n)}$ for every $n \in \mathbb{Z}$. Primitivity implies that each Fourier coefficient is $\overline{\chi}(n)\tau(\chi)$, including the vanishing when $n$ is not coprime to $q$. [Parseval's identity](/theorems/434) for the finite cyclic group $\mathbb{Z}/q\mathbb{Z}$ then compares the squared $L^2$ norm of these Fourier coefficients with the squared $L^2$ norm of $\chi$, forcing $|\tau(\chi)|^2=q$. [/proofplan] [step:Define the finite Fourier coefficients of $\chi$ modulo $q$] Define the additive character \begin{align*} e_q: \mathbb{Z} &\to \mathbb{C} \\ a &\mapsto \exp\left(\frac{2\pi i a}{q}\right). \end{align*} Define the finite Fourier transform of $\chi$ modulo $q$ by \begin{align*} \widehat{\chi}: \{1,\dots,q\} &\to \mathbb{C} \\ n &\mapsto \sum_{r=1}^{q} \chi(r)e_q(nr). \end{align*} With this notation, $\tau(\chi)=\widehat{\chi}(1)$. [/step] [step:Show that the Fourier coefficients are $\overline{\chi}(n)\tau(\chi)$] We claim that for every $n \in \{1,\dots,q\}$, \begin{align*} \widehat{\chi}(n)=\overline{\chi}(n)\tau(\chi). \end{align*} First suppose $\gcd(n,q)=1$. Let $b \in \mathbb{Z}$ be an inverse of $n$ modulo $q$, so $bn \equiv 1 \pmod q$. Multiplication by $n$ permutes the residue classes modulo $q$, so the substitution $s \equiv nr \pmod q$ gives \begin{align*} \widehat{\chi}(n) &= \sum_{s=1}^{q} \chi(bs)e_q(s) \\ &= \chi(b)\sum_{s=1}^{q}\chi(s)e_q(s). \end{align*} Since $\chi(n)$ is a complex root of unity and $\chi(b)=\chi(n)^{-1}$, we have $\chi(b)=\overline{\chi}(n)$. Therefore \begin{align*} \widehat{\chi}(n)=\overline{\chi}(n)\tau(\chi). \end{align*} Now suppose $\gcd(n,q)=d>1$. Set $m:=q/d$, so $m$ is a proper divisor of $q$. [claim:Primitivity gives a nontrivial unit congruent to $1$ modulo $m$] There exists an integer $a$ such that $\gcd(a,q)=1$, $a\equiv 1\pmod m$, and $\chi(a)\ne 1$. [/claim] [proof] Suppose instead that $\chi(a)=1$ for every integer $a$ satisfying $\gcd(a,q)=1$ and $a\equiv 1\pmod m$. We show that $\chi$ is induced from a character modulo $m$, contradicting the primitivity of $\chi$ modulo $q$. For every unit residue class $u\in (\mathbb{Z}/m\mathbb{Z})^\times$, choose an integer $A_u$ such that $A_u\equiv u\pmod m$ and $\gcd(A_u,q)=1$. Such a lift exists by choosing, for each prime $p\mid q$, a residue not divisible by $p$ and compatible with $u\pmod m$. Define \begin{align*} \psi: (\mathbb{Z}/m\mathbb{Z})^\times &\to \mathbb{C}^\times \\ u &\mapsto \chi(A_u). \end{align*} If $A_u$ and $B_u$ are two unit lifts of the same class $u$, then $A_uB_u^{-1}\equiv 1\pmod m$ in the unit group modulo $q$, so the assumed invariance gives $\chi(A_uB_u^{-1})=1$. Hence $\chi(A_u)=\chi(B_u)$, and $\psi$ is well-defined. It is multiplicative because $\chi$ is multiplicative on unit classes. The restriction of $\chi$ to $(\mathbb Z/q\mathbb Z)^\times$ therefore factors through the reduction map \begin{align*} (\mathbb Z/q\mathbb Z)^\times\to(\mathbb Z/m\mathbb Z)^\times. \end{align*} Equivalently, $\chi$ is induced from the character $\psi$ modulo $m$: on unit classes modulo $q$ it is obtained by reducing modulo $m$, and on non-units modulo $q$ it is zero by the definition of a Dirichlet character modulo $q$. Thus $\chi$ is induced from modulus $m<q$, contradicting primitivity. Therefore such an $a$ exists. [/proof] Because $d \mid n$ and $m=q/d \mid a-1$, we have $q \mid n(a-1)r$ for every $r \in \mathbb{Z}$. Hence \begin{align*} e_q(nar)=e_q(nr) \end{align*} for every $r \in \mathbb{Z}$. Multiplication by $a$ permutes the residue classes modulo $q$, so \begin{align*} \widehat{\chi}(n) &= \sum_{r=1}^{q}\chi(ar)e_q(nar) \\ &= \chi(a)\sum_{r=1}^{q}\chi(r)e_q(nr) \\ &= \chi(a)\widehat{\chi}(n). \end{align*} Since $\chi(a)\ne 1$, this forces $\widehat{\chi}(n)=0$. Also $\chi(n)=0$ because $\gcd(n,q)>1$, so \begin{align*} \widehat{\chi}(n)=0=\overline{\chi}(n)\tau(\chi). \end{align*} Thus the identity holds for all $n \in \{1,\dots,q\}$. [guided] We want to understand all Fourier coefficients of $\chi$ in terms of the single Gauss sum $\tau(\chi)$. The key point is that multiplication by a unit modulo $q$ permutes the residue classes, while primitivity controls what happens when the frequency is not a unit. For $n$ coprime to $q$, choose an integer $b$ satisfying $bn \equiv 1 \pmod q$. The change of variables $s \equiv nr \pmod q$ is valid because multiplication by $n$ is a bijection on $\mathbb{Z}/q\mathbb{Z}$. Therefore \begin{align*} \widehat{\chi}(n) &= \sum_{r=1}^{q}\chi(r)e_q(nr) \\ &= \sum_{s=1}^{q}\chi(bs)e_q(s) \\ &= \chi(b)\sum_{s=1}^{q}\chi(s)e_q(s) \\ &= \chi(b)\tau(\chi). \end{align*} Since $\chi(n)$ is a root of unity when $\gcd(n,q)=1$, its inverse equals its complex conjugate. Also $\chi(b)=\chi(n)^{-1}$ because $bn \equiv 1 \pmod q$. Hence $\chi(b)=\overline{\chi}(n)$, and \begin{align*} \widehat{\chi}(n)=\overline{\chi}(n)\tau(\chi). \end{align*} Now let $\gcd(n,q)=d>1$ and set $m=q/d$. The additive character $r \mapsto e_q(nr)$ has period dividing $m$. We need a unit $a$ that is congruent to $1$ modulo this period but on which $\chi$ is nontrivial. Why does such an $a$ exist? Suppose no such $a$ existed. Then $\chi(a)=1$ for every unit $a$ modulo $q$ satisfying $a\equiv 1\pmod m$. This would mean that $\chi$ cannot distinguish two unit classes modulo $q$ that reduce to the same unit class modulo $m$: if $A\equiv B\pmod m$ and both $A$ and $B$ are units modulo $q$, then $AB^{-1}\equiv 1\pmod m$, so $\chi(A)\chi(B)^{-1}=\chi(AB^{-1})=1$. Hence the value of $\chi(A)$ would depend only on $A\pmod m$. Formally, for each $u\in (\mathbb{Z}/m\mathbb{Z})^\times$, choose a unit lift $A_u$ modulo $q$ with $A_u\equiv u\pmod m$; such a lift exists by choosing residues prime to each prime divisor of $q$. Define \begin{align*} \psi: (\mathbb{Z}/m\mathbb{Z})^\times &\to \mathbb{C}^\times \\ u &\mapsto \chi(A_u). \end{align*} The preceding paragraph proves that $\psi$ is well-defined, and multiplicativity follows from multiplicativity of $\chi$. Thus the restriction of $\chi$ to the unit group modulo $q$ factors through reduction modulo $m$. Extending the resulting character modulo $m$ to a character modulo $q$ in the induced-character sense, namely by reducing unit classes and assigning $0$ to non-units modulo $q$, recovers $\chi$. That contradicts the assumption that $\chi$ is primitive modulo $q$. Therefore there exists an integer $a$ with $\gcd(a,q)=1$, $a\equiv 1\pmod m$, and $\chi(a)\ne 1$. For this $a$, the congruence $a\equiv 1 \pmod m$ means $a-1=mk$ for some $k\in\mathbb{Z}$. Since $n=dn_0$ for some $n_0\in\mathbb{Z}$, we get \begin{align*} n(a-1)r = dn_0mk r = q n_0 k r, \end{align*} so $q \mid n(a-1)r$. Hence $e_q(nar)=e_q(nr)$ for every integer $r$. Multiplication by $a$ still permutes the residue classes modulo $q$ because $\gcd(a,q)=1$, and therefore \begin{align*} \widehat{\chi}(n) &= \sum_{r=1}^{q}\chi(ar)e_q(nar) \\ &= \chi(a)\sum_{r=1}^{q}\chi(r)e_q(nr) \\ &= \chi(a)\widehat{\chi}(n). \end{align*} Since $\chi(a)\ne 1$, the equality $\widehat{\chi}(n)=\chi(a)\widehat{\chi}(n)$ implies $\widehat{\chi}(n)=0$. In the same case $\gcd(n,q)>1$, the Dirichlet character satisfies $\chi(n)=0$, so this is exactly \begin{align*} \widehat{\chi}(n)=\overline{\chi}(n)\tau(\chi). \end{align*} Thus the Fourier coefficient identity holds for every residue class $n$ modulo $q$. [/guided] [/step] [step:Prove finite Parseval for the chosen Fourier normalization] We prove the finite [Parseval identity](/theorems/248) for this normalization of the finite Fourier transform: \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 = q\sum_{r=1}^{q}|\chi(r)|^2. \end{align*} Expanding the left-hand side gives \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 &= \sum_{n=1}^{q} \left(\sum_{r=1}^{q}\chi(r)e_q(nr)\right) \overline{ \left(\sum_{s=1}^{q}\chi(s)e_q(ns)\right) } \\ &= \sum_{r=1}^{q}\sum_{s=1}^{q}\chi(r)\overline{\chi(s)} \sum_{n=1}^{q}e_q(n(r-s)). \end{align*} The inner sum satisfies \begin{align*} \sum_{n=1}^{q}e_q(n(r-s)) = \begin{cases} q, & r\equiv s \pmod q,\\ 0, & r\not\equiv s \pmod q, \end{cases} \end{align*} by the finite geometric-series formula. Since $r,s\in\{1,\dots,q\}$, the congruence $r\equiv s\pmod q$ is equivalent to $r=s$. Hence \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 = q\sum_{r=1}^{q}|\chi(r)|^2. \end{align*} [guided] We now prove the finite Parseval identity in the exact normalization used here, so no external Fourier-analysis convention is being imported. The finite Fourier coefficient is \begin{align*} \widehat{\chi}(n)=\sum_{r=1}^{q}\chi(r)e_q(nr), \end{align*} and therefore \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 &= \sum_{n=1}^{q} \left(\sum_{r=1}^{q}\chi(r)e_q(nr)\right) \overline{ \left(\sum_{s=1}^{q}\chi(s)e_q(ns)\right) } \\ &= \sum_{r=1}^{q}\sum_{s=1}^{q}\chi(r)\overline{\chi(s)} \sum_{n=1}^{q}e_q(n(r-s)). \end{align*} The only point to check is the inner additive-character sum. If $r\equiv s\pmod q$, then every summand is $1$, so the sum is $q$. If $r\not\equiv s\pmod q$, set $\zeta:=e_q(r-s)$. Then $\zeta\ne 1$ and $\zeta^q=1$, so the finite geometric-series formula gives \begin{align*} \sum_{n=1}^{q}e_q(n(r-s)) = \sum_{n=1}^{q}\zeta^n = \zeta\frac{1-\zeta^q}{1-\zeta} =0. \end{align*} Thus \begin{align*} \sum_{n=1}^{q}e_q(n(r-s)) = \begin{cases} q, & r\equiv s \pmod q,\\ 0, & r\not\equiv s \pmod q. \end{cases} \end{align*} Because $r,s\in\{1,\dots,q\}$, the congruence $r\equiv s\pmod q$ is equivalent to equality $r=s$. Substituting this orthogonality relation into the expanded sum leaves only the diagonal terms: \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 = q\sum_{r=1}^{q}\chi(r)\overline{\chi(r)} = q\sum_{r=1}^{q}|\chi(r)|^2. \end{align*} This is exactly the finite Parseval identity needed for the comparison step. [/guided] [/step] [step:Compare both evaluations and extract the square root] By the Fourier coefficient identity proved above, \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 &= \sum_{n=1}^{q}|\overline{\chi}(n)\tau(\chi)|^2 \\ &= |\tau(\chi)|^2\sum_{n=1}^{q}|\chi(n)|^2. \end{align*} A Dirichlet character modulo $q$ has $|\chi(n)|=1$ when $\gcd(n,q)=1$ and $|\chi(n)|=0$ otherwise. Therefore \begin{align*} \sum_{n=1}^{q}|\chi(n)|^2=\varphi(q), \end{align*} where $\varphi(q)$ is Euler's totient function. Since $\varphi(q)>0$, comparing this with Parseval gives \begin{align*} |\tau(\chi)|^2\varphi(q)=q\varphi(q). \end{align*} Dividing by $\varphi(q)$ yields \begin{align*} |\tau(\chi)|^2=q. \end{align*} Both sides are non-negative [real numbers](/page/Real%20Numbers), so taking the non-negative square root gives \begin{align*} |\tau(\chi)|=\sqrt{q}. \end{align*} This is the desired formula. [guided] We now combine the two evaluations of the same quantity, namely \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2. \end{align*} From the Fourier coefficient identity proved earlier, each coefficient satisfies $\widehat{\chi}(n)=\overline{\chi}(n)\tau(\chi)$. Hence \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 &= \sum_{n=1}^{q}|\overline{\chi}(n)\tau(\chi)|^2 \\ &= |\tau(\chi)|^2\sum_{n=1}^{q}|\chi(n)|^2. \end{align*} A Dirichlet character modulo $q$ is a group character on the unit classes and is extended by $0$ on non-units. Therefore $|\chi(n)|=1$ when $\gcd(n,q)=1$ and $|\chi(n)|=0$ when $\gcd(n,q)>1$. It follows that \begin{align*} \sum_{n=1}^{q}|\chi(n)|^2=\varphi(q), \end{align*} where $\varphi(q)$ denotes Euler's totient function, the number of integers in $\{1,\dots,q\}$ that are coprime to $q$. The Parseval computation gives the second evaluation \begin{align*} \sum_{n=1}^{q}|\widehat{\chi}(n)|^2 = q\sum_{n=1}^{q}|\chi(n)|^2 = q\varphi(q). \end{align*} Comparing the two evaluations gives \begin{align*} |\tau(\chi)|^2\varphi(q)=q\varphi(q). \end{align*} Since $q\ge 1$, Euler's totient satisfies $\varphi(q)>0$, so division by $\varphi(q)$ is valid. We obtain \begin{align*} |\tau(\chi)|^2=q. \end{align*} Finally, $|\tau(\chi)|$ and $\sqrt q$ are both non-negative real numbers, so taking the non-negative square root yields \begin{align*} |\tau(\chi)|=\sqrt{q}. \end{align*} This proves the theorem. [/guided] [/step]