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.