Strengthening of Dirichlet's theorem on arithmetic progressions

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 ?

• 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