set of primes plus 1 contain multiples of every integer Saw a claim that for every natural number $j$, the set $\{ nj-1: n \ge 1 \} $ must contain at least one prime. Is that correct? If so, is there a simple proof? I can see that at least one can be easily extended to infinitely many, if the statement is correct. 
 A: See https://mathoverflow.net/questions/32624/special-cases-of-dirichlets-theorem and the many links given there. In particular, I quote from Robin Chapman's answer: 
...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.
EDIT. One of the links at the mathoverflow question leads to Keith Conrad's paper, Euclidean proofs of Dirichlet's Theorem. Conrad cites a theorem of Schur: if $a^2\equiv1\bmod m$, then a Euclidean polynomial for $a\bmod m$ exists (he also cites a theorem of Murty: if there is a Euclidean polynomial for $a\bmod m$, then $a^2\equiv1\bmod m$). The Schur citation is Uber die Existenz unendlich vieler Primzahlen in einigen speziellen arithmetischen Progressionen, Sitzungber. Berliner Math. Ges. 11 (1912), 40–50.
MORE EDIT. I had a look at the proof in Nagell. The good news, it doesn't use anything beyond introductory Number Theory, Binomial Theorem, and arithmetic of complex numbers. Bad news, it's three pages long, and that's not counting a page for the proof of one of the earlier theorems used in the proof. So, I'm not inclined to write it out here. 
