[proofplan] We split the proof according to whether $n$ is coprime to $q$. If $\gcd(n,q)>1$, the extension convention for Dirichlet characters makes every term on the right-hand side vanish. If $\gcd(n,q)=1$, then $a$ and $n$ define elements of the unit group $(\mathbb{Z}/q\mathbb{Z})^\times$, and the desired identity is exactly the character orthogonality relation on that finite abelian group, applied to the quotient residue class $n a^{-1}$. [/proofplan] [step:Handle integers outside the reduced residue classes] Assume first that $\gcd(n,q)>1$. By the definition of a Dirichlet character modulo $q$ as a character on $(\mathbb{Z}/q\mathbb{Z})^\times$ extended by zero away from the reduced residue classes, every $\chi \in \mathcal{X}(q)$ satisfies $\chi(n)=0$. Hence \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \in \mathcal{X}(q)} \overline{\chi(a)}\,\chi(n) = \frac{1}{\varphi(q)}\sum_{\chi \in \mathcal{X}(q)} \overline{\chi(a)} \cdot 0 = 0. \end{align*} By the stated convention for the left-hand side, $\mathbb{1}_{\{n \equiv a \pmod q\}}=0$ whenever $\gcd(n,q)>1$. Thus the identity holds in this case. [/step] [step:Reduce the coprime case to orthogonality on the unit group] Assume now that $\gcd(n,q)=1$. Let \begin{align*} G := (\mathbb{Z}/q\mathbb{Z})^\times \end{align*} be the finite abelian group of reduced residue classes modulo $q$, and let $\bar{a},\bar{n} \in G$ denote the residue classes of $a$ and $n$. Since $\gcd(a,q)=1$, the class $\bar{a}$ has an inverse $\bar{a}^{-1} \in G$. Define \begin{align*} u := \bar{n}\bar{a}^{-1} \in G. \end{align*} For every $\chi \in \mathcal{X}(q)$, the restriction of $\chi$ to $G$ is a group homomorphism $G \to \mathbb{C}^\times$. Therefore $\chi(a)$ is a root of unity, so $\overline{\chi(a)}=\chi(a)^{-1}=\chi(a^{-1})$, where $a^{-1}$ denotes any integer representative of $\bar{a}^{-1}$. Hence \begin{align*} \overline{\chi(a)}\,\chi(n) = \chi(a)^{-1}\chi(n) = \chi(n a^{-1}) = \chi(u). \end{align*} Thus \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \in \mathcal{X}(q)} \overline{\chi(a)}\,\chi(n) = \frac{1}{|G|}\sum_{\chi \in \mathcal{X}(q)} \chi(u), \end{align*} because $|G|=\varphi(q)$. [guided] Now we are in the reduced case, so both $a$ and $n$ represent units modulo $q$. This lets us divide by $a$ inside the multiplicative group of reduced residue classes. Let \begin{align*} G := (\mathbb{Z}/q\mathbb{Z})^\times. \end{align*} The residue classes $\bar{a},\bar{n} \in G$ are well-defined units because $\gcd(a,q)=1$ and $\gcd(n,q)=1$. Since $\bar{a}$ is a unit, it has an inverse $\bar{a}^{-1} \in G$. We set \begin{align*} u := \bar{n}\bar{a}^{-1} \in G. \end{align*} The point of introducing $u$ is that the congruence $n \equiv a \pmod q$ is equivalent to $u$ being the identity element of $G$. For each Dirichlet character $\chi \in \mathcal{X}(q)$, the restriction $\chi|_G: G \to \mathbb{C}^\times$ is a group homomorphism. Hence $\chi(a)$ has finite multiplicative order and therefore lies on the unit circle. Consequently \begin{align*} \overline{\chi(a)}=\chi(a)^{-1}. \end{align*} Choosing any integer representative $a^{-1}$ of $\bar{a}^{-1}$, multiplicativity gives \begin{align*} \overline{\chi(a)}\,\chi(n) = \chi(a)^{-1}\chi(n) = \chi(a^{-1})\chi(n) = \chi(n a^{-1}) = \chi(u). \end{align*} Since the number of reduced residue classes modulo $q$ is $\varphi(q)$, we have $|G|=\varphi(q)$, and therefore \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \in \mathcal{X}(q)} \overline{\chi(a)}\,\chi(n) = \frac{1}{|G|}\sum_{\chi \in \mathcal{X}(q)} \chi(u). \end{align*} [/guided] [/step] [step:Apply the finite character orthogonality relation] We use the finite abelian character orthogonality relation: for a finite abelian group $G$ and an element $u \in G$, \begin{align*} \sum_{\psi \in \widehat{G}} \psi(u) = \begin{cases} |G|, & u=e_G,\\ 0, & u \ne e_G, \end{cases} \end{align*} where $\widehat{G}$ is the character group of $G$ and $e_G$ is the identity element of $G$ (citing a result not yet in the wiki: finite abelian character orthogonality). The Dirichlet characters modulo $q$ are precisely the characters of $G=(\mathbb{Z}/q\mathbb{Z})^\times$ extended by zero away from the reduced residue classes. Applying this orthogonality relation to the element $u=\bar{n}\bar{a}^{-1}$ gives \begin{align*} \frac{1}{|G|}\sum_{\chi \in \mathcal{X}(q)} \chi(u) = \begin{cases} 1, & u=e_G,\\ 0, & u \ne e_G. \end{cases} \end{align*} Since $u=e_G$ is equivalent to $\bar{n}=\bar{a}$ in $(\mathbb{Z}/q\mathbb{Z})^\times$, this is equivalent to $n \equiv a \pmod q$. Therefore \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \in \mathcal{X}(q)} \overline{\chi(a)}\,\chi(n) = \mathbb{1}_{\{n \equiv a \pmod q\}}. \end{align*} [guided] We now use the basic orthogonality law for characters of a finite abelian group. It says that if $G$ is a finite abelian group and $u \in G$, then \begin{align*} \sum_{\psi \in \widehat{G}} \psi(u) = \begin{cases} |G|, & u=e_G,\\ 0, & u \ne e_G, \end{cases} \end{align*} where $\widehat{G}$ is the group of homomorphisms $\psi: G \to \mathbb{C}^\times$ and $e_G$ is the identity element of $G$ (citing a result not yet in the wiki: finite abelian character orthogonality). The hypotheses of this orthogonality relation are satisfied here because \begin{align*} G=(\mathbb{Z}/q\mathbb{Z})^\times \end{align*} is a finite abelian group under multiplication of residue classes, and the set $\mathcal{X}(q)$ of Dirichlet characters modulo $q$ is exactly the character group $\widehat{G}$ after extending each character by zero on integers not coprime to $q$. Applying the orthogonality relation to \begin{align*} u=\bar{n}\bar{a}^{-1} \in G \end{align*} gives \begin{align*} \frac{1}{|G|}\sum_{\chi \in \mathcal{X}(q)} \chi(u) = \begin{cases} 1, & u=e_G,\\ 0, & u \ne e_G. \end{cases} \end{align*} The condition $u=e_G$ means \begin{align*} \bar{n}\bar{a}^{-1}=e_G. \end{align*} Multiplying both sides by $\bar{a}$ inside $G$ gives $\bar{n}=\bar{a}$, which is exactly the congruence $n \equiv a \pmod q$. Therefore \begin{align*} \frac{1}{|G|}\sum_{\chi \in \mathcal{X}(q)} \chi(u) = \mathbb{1}_{\{n \equiv a \pmod q\}}. \end{align*} Combining this with the reduction \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \in \mathcal{X}(q)} \overline{\chi(a)}\,\chi(n) = \frac{1}{|G|}\sum_{\chi \in \mathcal{X}(q)} \chi(u) \end{align*} proves the desired identity in the coprime case. [/guided] [/step] [step:Combine the two cases] The first step proves the identity when $\gcd(n,q)>1$, and the preceding step proves it when $\gcd(n,q)=1$. These two cases exhaust all integers $n \in \mathbb{Z}$, so the formula holds for every $n \in \mathbb{Z}$. [/step]