2

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.

Co-ordinator
  • 93

1 Answers1

1

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.

Gerry Myerson
  • 179,216
  • 1
    If the proof is simple it would be nice to include it in your answer. – orlp Jul 29 '17 at 13:24
  • @orlp, elementary $\ne$ simple. But let me encourage you to track down a copy of Nagell's book and see whether you would like to post an answer with the proof. – Gerry Myerson Jul 29 '17 at 13:27
  • 1
    The question asked for a simple proof though. So even if it's elementary, if it's not simple (although it's subjective what exactly can be considered simple) it doesn't answer the question. – orlp Jul 29 '17 at 13:30
  • @GerryMyerson: Thanks for the pointers. – Co-ordinator Jul 29 '17 at 17:49
  • @orlp: While I did ask for a simple proof, I guess a standard one does fine! – Co-ordinator Jul 29 '17 at 17:50
  • @orlp, if after all these years the only proof anyone can point to is not simple, that answers the question in the negative. At least, it would strongly suggest that there is no simple proof. Again I encourage you to follow the pointers I've given, and see for yourself what the situation is. – Gerry Myerson Jul 29 '17 at 23:48