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

The number of primes in each of the $\phi(n)$ residue classes relatively prime to $n$ are known to occur with asymptotically equal frequency (following from the proof of the Prime Number Theorem). Does the same result hold on pairs of consecutive primes on the $\phi(n)^2$ pairs of congruence classes?

To wit: Consider $\{(2, 3), (3, 5), (5, 7), (7, 11), \ldots\}\pmod n$. Does $(a,b)$ occur with natural density $$\begin{cases} 1/\phi(n)^2,&\gcd(ab,n)=1\\ 0,&\text{otherwise} \end{cases} $$ ?

share|cite|improve this question
If this question is meant to accidentally generalize questions such as the infinitude of twin primes, then it is very hard... but the answer is conjecturally "yes". I am insufficiently expert to know state-of-the-art. – paul garrett Jan 2 '13 at 16:53
@paulgarrett: It does not suffice to show the existence of infinitely many twin primes. It could show that there are infinitely many consecutive primes (p, q) with p = 5 mod 6 and q = 1 mod 6, but it can't distinguish the case q = p + 2 and the case q = p + 8 with p + 2 composite. – Charles Jan 2 '13 at 16:56
Ok, then the precise meaning/intent of the question is not entirely clear to me... – paul garrett Jan 2 '13 at 17:08
@paulgarrett: Consider {(2, 3), (3, 5), (5, 7), (7, 11), ...} mod n. Assuming $\gcd(ab, n)=1$, does $(a, b)$ occur with natural density $1/\phi(n)^2$? – Charles Jan 2 '13 at 18:02
Thanks for clarification! – paul garrett Jan 2 '13 at 18:06

I think it would be extremely unlikely that, at this point in time, one could prove anything of this kind. Even the much weaker problem (for general $n$) of whether there are infinitely many such pairs (if $\gcd(ab,n) = 1$) seems extremely difficult as soon as $\phi(n) > 2$.

Consider the very special case that $n = 4$. If $\pi_1(x)$ and $\pi_3(x)$ denote the prime counting function for primes congruent to $1$ and $3$ mod $4$ respectively, the fact that:

$$\limsup(\pi_1(x) - \pi_3(x)) = \infty, \qquad \limsup (\pi_3(x) - \pi_1(x)) = \infty$$

implies that there are infinitely many such pairs for any $(a,b)$ mod $4$ with $ab$ odd. However, such results are completely insufficient for showing that there are infinitely many triples (say) of consecutive primes which are $1$ mod $4$. Similarly, the problem for pairs of primes when $\phi(n) > 2$ seems very difficult. It seems to me that the only approach to such problems is via generalizations of the twin prime conjecture, and (at best) such results will never give positive density.

To summarize: as a general heuristic, of course, your conjecture seems quite reasonable, but even the weaker conjecture (that there are infinitely many pairs for all suitable $a$ and $b$) seems out of reach unless $n = 3$, $4$, or $6$.

share|cite|improve this answer

I suspect that the statement is false. The effect of prime gaps making some sizes more likely than others disappears after about $e^{e^n},$ but the effect of (small) primes dividing the modulus seems to be a problem except when $n$ is a prime power.

So the conjecture could either be weakened to the case where $n=p^k$ or the density corrected with an appropriate product over primes.

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.