Can Dirichlet characters mod q only agree on the same congruence class?

Question

In my lecture notes for an analytic number theory module, the lecturer (I think) implicitly uses that, for $(a,q)=1$, if $\chi(a)=\chi(n)$ for all Dirichlet characters $\chi\mod q$, then $n\equiv a \mod q$. Looking at the table of the first few characters on Wikipedia, I can believe this is true. So, is this true? And if so, how would I prove it?

Answer 1

The Dirichlet characters $\bmod q$ correspond to the characters $\Bbb{Z/qZ^\times\to C^\times}$. Given some $b\ne 1\in \Bbb{Z/qZ^\times}$ (here $b= an^{-1}$) start with $H_1=\langle b\rangle$ and a non-trivial character $\chi_1$ of $H_1$, then for $k=1,2,\ldots$, take $x_{k+1}\not \in H_k$, let $H_{k+1}=\langle H_k,x_{k+1}\rangle$, let $e_{k+1}$ be the least natural number such that $x_{k+1}^{e_{k+1}}\in H_k$ and set $\chi_{k+1}(x_{k+1}) = \chi_k(x_{k+1})^{1/e_{k+1}}$.

At some point there is no such $x_{k+1}$ and $\chi_k$ is a character of $\Bbb{Z/qZ^\times}$ such that $\chi_k(b)\ne 1$. Moreover if $\langle b\rangle$ was a maximal cyclic subgroup and $\chi_1(b)$ had the same order as $b$ then $G=\langle b\rangle\times \ker(\chi_k)$.

Answer 2

In addition to @reuns' to-the-point answer, the is a slight generalization that perhaps shows what's really at play.

E.g., for a finite abelian group $A$, the collection $\mathbb C(A)$ of complex-valued functions on $A$ has basis consisting of the group homomorphisms $A\to \mathbb C^\times$.

And, part of the point (to my mind) is that there is a (reasonable) proof that does not depend on the structure theorem for finitely-generated abelian groups. Rather, we use the spectral theorem for mutually commuting unitary operators on finite-dimensional (complex) vector spaces. With these hints, it's not hard to contrive such a proof.