# If $k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.

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.

• I don't understand why you need such a strong statement to prove your original claim. – Sandeep Silwal Apr 20 '14 at 4:30
• en.wikipedia.org/wiki/… – Will Jagy Apr 20 '14 at 4:37