[proofplan] We expand the indicator of the reduced residue class $a \pmod q$ using the orthogonality of Dirichlet characters modulo $q$. Multiplying that identity by $a_n$ and summing over the finite interval gives a character expansion for $A(q,a)$. The term corresponding to the principal character is exactly $A_0(q)/\varphi(q)$, so subtracting it leaves precisely the non-principal character contribution. [/proofplan] [step:Express the reduced residue class indicator as a character average] Let $G := (\mathbb{Z}/q\mathbb{Z})^\times$ be the multiplicative group of reduced residue classes modulo $q$, and let $\widehat{G}$ denote its character group. The Dirichlet characters modulo $q$ are exactly the functions $\chi: \mathbb{Z} \to \mathbb{C}$ obtained from characters of $G$ on integers coprime to $q$, extended by $\chi(n)=0$ when $\gcd(n,q)>1$. For every integer $n \in \mathbb{Z}$, we claim that the character average equals the reduced residue class indicator. Explicitly, if $n \equiv a \pmod q$, then \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \bmod q}\overline{\chi(a)}\chi(n)=1. \end{align*} If $n \not\equiv a \pmod q$, then \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \bmod q}\overline{\chi(a)}\chi(n)=0. \end{align*} If $\gcd(n,q)>1$, then $\chi(n)=0$ for every Dirichlet character $\chi \bmod q$, and since $\gcd(a,q)=1$ the congruence $n \equiv a \pmod q$ cannot hold. Thus both sides are $0$. Assume now that $\gcd(n,q)=1$. Let $[n] \in G$ and $[a] \in G$ be the residue classes of $n$ and $a$. Since each $\chi$ is multiplicative on $G$ and $|\chi(a)|=1$, we have \begin{align*} \overline{\chi(a)}\chi(n)=\chi([n][a]^{-1}). \end{align*} We use the following finite character orthogonality calculation, proved here for the group $G$. [claim:Characters of $G$ sum to zero away from the identity] For every $g \in G$, \begin{align*} \sum_{\chi \in \widehat{G}} \chi(g)=\varphi(q)\mathbb{1}_{\{1_G\}}(g). \end{align*} [/claim] [proof] If $g=1_G$, then every character satisfies $\chi(1_G)=1$, and $|\widehat{G}|=|G|=\varphi(q)$, so the sum is $\varphi(q)$. Assume $g\ne 1_G$. Since $G$ is a finite abelian group, decompose $G$ as a finite product of cyclic groups and choose a coordinate on which $g$ has non-identity component. Projection to that cyclic factor followed by a nontrivial root-of-unity character gives a character $\psi\in\widehat{G}$ with $\psi(g)\ne 1$. Let \begin{align*} S(g)=\sum_{\chi\in\widehat{G}}\chi(g). \end{align*} Multiplication by $\psi$ is a bijection of $\widehat{G}$, hence \begin{align*} S(g)=\sum_{\chi\in\widehat{G}}(\psi\chi)(g)=\psi(g)S(g). \end{align*} Since $\psi(g)\ne 1$, this forces $S(g)=0$. [/proof] Applying the claim with $g=[n][a]^{-1}$ gives $\varphi(q)$ when $[n][a]^{-1}=1_G$ and gives $0$ otherwise. The condition $[n][a]^{-1}=1_G$ is equivalent to $n \equiv a \pmod q$, so division by $\varphi(q)$ gives the claimed identity. [guided] The goal of this step is to replace a congruence condition by a sum over characters. Define $G := (\mathbb{Z}/q\mathbb{Z})^\times$, the multiplicative group of reduced residue classes modulo $q$, and let $\widehat{G}$ be its group of complex-valued characters. A Dirichlet character modulo $q$ is a character on $G$, read as a function on integers coprime to $q$, and extended by $0$ on integers not coprime to $q$. We prove that for every integer $n$, the character average equals the reduced residue class indicator. Explicitly, if $n \equiv a \pmod q$, then \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \bmod q}\overline{\chi(a)}\chi(n)=1. \end{align*} If $n \not\equiv a \pmod q$, then \begin{align*} \frac{1}{\varphi(q)}\sum_{\chi \bmod q}\overline{\chi(a)}\chi(n)=0. \end{align*} First suppose $\gcd(n,q)>1$. Then every Dirichlet character modulo $q$ satisfies $\chi(n)=0$, so the character average is $0$. Also $n \not\equiv a \pmod q$, because $\gcd(a,q)=1$ and any integer congruent to $a$ modulo $q$ is also coprime to $q$. Hence the indicator on the right-hand side is also $0$. Now suppose $\gcd(n,q)=1$. Then both $[n]$ and $[a]$ are elements of $G$. Since $\chi(a)$ lies on the unit circle, $\overline{\chi(a)}=\chi(a)^{-1}=\chi([a]^{-1})$. Multiplicativity gives \begin{align*} \overline{\chi(a)}\chi(n)=\chi([a]^{-1})\chi([n])=\chi([n][a]^{-1}). \end{align*} We now justify the finite character orthogonality relation rather than treating it as a black box. For $g\in G$, define \begin{align*} S(g)=\sum_{\chi\in\widehat{G}}\chi(g). \end{align*} If $g=1_G$, then every character has value $1$, and there are $|G|=\varphi(q)$ characters, so $S(1_G)=\varphi(q)$. If $g\ne 1_G$, the finite abelian structure of $G$ gives a character $\psi\in\widehat{G}$ with $\psi(g)\ne 1$: decompose $G$ into cyclic factors, project to a factor where $g$ is nontrivial, and use a nontrivial root-of-unity character on that cyclic factor. Multiplication by this fixed character $\psi$ permutes $\widehat{G}$, so \begin{align*} S(g)=\sum_{\chi\in\widehat{G}}(\psi\chi)(g)=\psi(g)S(g). \end{align*} Because $\psi(g)\ne 1$, the equality forces $S(g)=0$. Apply this with $g=[n][a]^{-1}$. If $[n][a]^{-1}=1_G$, then \begin{align*} \sum_{\chi \bmod q}\overline{\chi(a)}\chi(n)=\varphi(q). \end{align*} If $[n][a]^{-1}\ne 1_G$, then \begin{align*} \sum_{\chi \bmod q}\overline{\chi(a)}\chi(n)=0. \end{align*} Finally, $[n][a]^{-1}=1_G$ exactly means $[n]=[a]$, which is the congruence $n \equiv a \pmod q$. Dividing by $\varphi(q)$ proves the character-average formula for the reduced residue class indicator. [/guided] [/step] [step:Sum the indicator identity against the coefficients] Using the identity from the previous step and the definition of $A(q,a)$, we obtain \begin{align*} A(q,a)=\sum_{M<n\le M+N}a_n\left(\frac{1}{\varphi(q)}\sum_{\chi \bmod q}\overline{\chi(a)}\chi(n)\right). \end{align*} The interval contains finitely many integers, and there are finitely many characters modulo $q$, so the two sums may be interchanged: \begin{align*} A(q,a)=\frac{1}{\varphi(q)}\sum_{\chi \bmod q}\overline{\chi(a)}\sum_{M<n\le M+N}a_n\chi(n). \end{align*} [/step] [step:Identify and subtract the principal character contribution] Separate the principal character $\chi_0$ from the character sum: \begin{align*} A(q,a)=\frac{1}{\varphi(q)}\overline{\chi_0(a)}\sum_{M<n\le M+N}a_n\chi_0(n)+\frac{1}{\varphi(q)}\sum_{\chi \bmod q,\ \chi\ne\chi_0}\overline{\chi(a)}\sum_{M<n\le M+N}a_n\chi(n). \end{align*} Since $\gcd(a,q)=1$, the principal character satisfies $\chi_0(a)=1$. Also $\chi_0(n)=1$ when $\gcd(n,q)=1$ and $\chi_0(n)=0$ otherwise, hence \begin{align*} \sum_{M<n\le M+N}a_n\chi_0(n)=\sum_{M<n\le M+N,\ \gcd(n,q)=1}a_n=A_0(q). \end{align*} Therefore \begin{align*} A(q,a)=\frac{A_0(q)}{\varphi(q)}+\frac{1}{\varphi(q)}\sum_{\chi \bmod q,\ \chi\ne\chi_0}\overline{\chi(a)}\sum_{M<n\le M+N}a_n\chi(n). \end{align*} Subtracting $A_0(q)/\varphi(q)$ from both sides and using the definition \begin{align*} E(q,a)=A(q,a)-\frac{A_0(q)}{\varphi(q)} \end{align*} gives \begin{align*} E(q,a)=\frac{1}{\varphi(q)}\sum_{\chi \bmod q,\ \chi\ne\chi_0}\overline{\chi(a)}\sum_{M<n\le M+N}a_n\chi(n). \end{align*} This is the desired formula. [/step]