As Daniel has pointed out, there is an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv1$ (mod $n$). There is an also an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv-1$ (mod $n$). This can be found in Nagell's Introduction to Number Theory section 50 in the second edition.
Robin Chapman
- 20.8k
- 2
- 66
- 81