Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a known "elementary" proof that there are infinitely many primes congruent to 7 modulo 10?

Dirichlet's well known theorem gives that there are infinitely many such primes, as 10 and 7 are coprime. But Dirichlet's result is not "elementary" (even though one can in essence give a real variable proof. I am using elementary here in a somewhat intuitive sense).

There is a well-known result of Murty showing that there is no "Euclidean" proof of this fact (see here and here).

One way of formalizing Murty's result is by saying that, for $a,m$ relatively prime, a polynomial for $a,m$ is a $p\in{\mathbb Z}[x]$ such that for all but finitely many $n$, the prime factors of $p(n)$ are congruent to 1 or $a$ modulo $m$ and, infinitely often, the second possibility occurs. Murty argues that "Euclidean" proofs all produce such polynomials, and his proof gives that if there is such a $p$, then $a^2\equiv 1\pmod m$. In particular, there is no polynomial for $2,5$, so there is no Euclidean proof that there are infinitely many primes of the form $5t+2$ or, equivalently, $10t+7$.

But an elementary proof does not need to be a "Euclidean" proof. I would settle for a proof that uses a modest amount of algebraic number theory.

I would even be happy if it turns out that no elementary proof is known, but a proof that does not require the full machinery of Dirichlet's theorem is possible.

Finally, I would also like to know of a source giving a more or less complete list of pairs $(a,b)$ for which there are known elementary proofs that there are infinitely many primes of the form $at+b$. I know Narkiewicz discusses some pairs in section 2.5 of his "The development of prime number theory" and refers to Dickson's "History of the theory of numbers". It may be these are the sources. But just in case there are some others, I would appreciate a reference.

share|cite|improve this question
I didn't know there was an elementary proof showing that are infinitely many primes of any kind! – Austin Henley Mar 1 '12 at 3:12
@Austin: There's an elementary proof that there are infinitely many primes; and there are elementary proofs that there are infinitely many primes of the form $4n+3$ and also of the form $4n+1$. The latter two proceed along similar lines as the first (take any finite list, construct a number that must be divisible by a prime of the desired form but which is not divisible by any number on the given list). – Arturo Magidin Mar 1 '12 at 3:32
up vote 6 down vote accepted

One thing: this MO discussion is relevant.

A second thing:

I know that you asked to avoid the machinery of Dirichlet's proof, but I just wanted to point out that this proof is not so complicated, except for the proof that $L(1,\chi) \neq 0$ when $\chi$ is a quadratic character. (See e.g. the treatment in Serre's Course in arithmetic, or any other text.)

But for any fixed choice of $a$ and $b$, this non-vanishing can be obtained in an elementary way. E.g. for primes of the form $5 t + 2$, the relevant quadratic Dirichlet series is $$1 - 1/2 - 1/3 + 1/4 + \cdots + 1/(5n+1) - 1/(5n+2) - 1/(5n+3) + 1/(5n+4) + \cdots,$$ and one can see this is positive, by noting that $1/(5n+1) - 1/(5n+2) - 1/(5n+3) + 1/(5n+4) = 1/(5n+1)(5n+2)-1/(5n+3)(5n+4) > 0.$

share|cite|improve this answer
Ah, OK. That's a very good point, thanks. This is a great way to address the question. – Bruce George Mar 1 '12 at 5:52

Some cases are done in Shay Gueron and Ran Tessler, Infinitely Many Primes in Arithmetic Progressions: The Cyclotomic Polynomial Method, The Mathematical Gazette Vol. 86, No. 505, Mar., 2002, pages 110-114. If you have jstor access, that's

share|cite|improve this answer
Thank you. I did not know about this reference. – Bruce George Mar 1 '12 at 5:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.