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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.