 Solution

Use the unitary discrete Fourier transform, with $e(x)=\exp (2\pi ix)$:For a unit $a$, substitute $m=an$ in the sum. The multiplicativity of the Dirichlet character gives $\chi (a^{-1}m)=\overline{\chi (a)}\chi (m)$, henceThe complex conjugation is present in the original PDF and lost in the converted TeX. It matters for nonreal characters.

Now let $q=p^k$ and let $\chi$ be primitive. Since it does not descend to $p^{k-1}$, there is a unit $u\equiv 1(\mathrm{mod}{p}^{k-1})$ with $\chi (u)\ne 1$. For $k=1$, reduction is to the unit group modulo one. If $p\mid a$, then $a(u-1)\equiv 0(\mathrm{mod}q)$, so multiplication of the summation variable by $u$ leaves its exponential factor unchanged. It follows that $\hat{\chi }(a)=\chi (u)\hat{\chi }(a)$, and therefore $\hat{\chi }(a)=0$. Also $\chi (a)=0$. This proves the formula at every nonunit as well as every unit, including $a=0$.