MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Hello all, Dirichlet's famous theorem asserts that any arithmetic progression $\lbrace ax+b | x \in {\mathbb N}\rbrace$ contains infinitely many primes if a and b are relatively prime.

I am wondering if the following strengthening of Dirichlet's theorem is also true :

Let $a,b$ be relatively prime integers as above. Then there is a uniform bound $g(a,b)$ such that any interval $\lbrace x+1,x+2, \ldots ,x+g(a,b)\rbrace$ of $g(a,b)$ successive integers contains at least one integer $y$ which is congruent to $b$ modulo $a$ and which is not divisible by any integer between $x+1$ (inclusive if $y\neq x+1$) and $y$ (exclusive).

Without the uniform bound, this would be a tasteless easy consequence of Dirichlet's theorem. With the bound, however, it becomes stronger than Dirichlet's theorem.

Perhaps the two are in fact equivalent ?

share|cite|improve this question
I don't understand how this statement is stronger than Dirichlet's theorem. – Qiaochu Yuan Mar 5 '10 at 6:13
If I understand correctly, your statement is implied by a seemingly weak version of Dirichlet's theorem. Given a,b, let p be a prime congruent to b mod a so that p>a. Let g(a,b) = p. If x<p, take y=p. If $x\geq p$, let y be the smallest number bigger than x that is congruent to b mod a. Then y is at most x+a, so y is not divisible by the numbers between x and y because they're too big: y<2x. – Jonas Meyer Mar 5 '10 at 7:58
@ Qiaochu : As you explained in your own question about Dirichlet's theorem, it suffices to show that there exists at least one prime congruent to b modulo a. Let A be the lcm of all the integers between 2 and a. There is a B coprime to A such that any number congruent to B modulo A is also congruent to b modulo a and is not divisble by any number <=a. We know that there is a y between a+1 and a+g(A,B), such that y is not divisible by any integer in [x+1,y-1] and y is congruent to B modulo A. It is readily seen that y is prime, qed. – Ewan Delanoy Mar 5 '10 at 15:31
@ Jonas : you're right. In fact, the optimal value of g(a,b) is exactly the smallest prime congruent to b modulo a. – Ewan Delanoy Mar 5 '10 at 15:41

This question has essentially been answered in the comments, so I see no reason for it to remain officially unanswered.

The proposed property holds. It is "equivalent to" Dirichlet's theorem, in the informal sense that each could be used to prove the other. However, we are not talking about axiomatization, so rather I would say that both are true and equivalence isn't meaningful. (This is not to be confused with Fréchet's objection to Tarski.)

This is community wiki, so feel free edit.

share|cite|improve this answer

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.