I need to use this result in a step of a proof, but I am for some reason unable to justify it. It seems to be true, after trying some examples, but I am not sure why.
If $1 \le k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.
It is unclear to me how one can check whether a number in $\{k+mn:m \in \mathbb{Z}\}$ is prime or not.
Context: I am trying to show that $$\{p: \text{$p$ prime, coprime to $n$}\}\stackrel{\text{mod } p}{\longrightarrow} \{k : 1 \le k \le n, \text{ $k$ coprime to $n$}\}$$ is a surjection. In particular, $\zeta=e^{2\pi i/n}$, and I want to show that the $\zeta^p$ (with $p$ coprime to $n$) are the primitive $n$th roots of unity.