Suppose we start with $k$ primes $p_1,p_2,\ldots ,p_k$ (not necessarily consecutive) and a residue class for each prime $r_1,r_2,\ldots ,r_k$.
We denote the least integer not covered by the arithmetic progressions $r_i+m\cdot p_i$ as $r_{k+1}$ which is going to be the new residue class for a (random) prime $p_{k+1}$.
We proceed in this way "covering" the natural numbers (without changing the $r_i$'s.)
Question:Is it true that $\sum\limits_{n=1}^\infty\frac{1}{r_n}=+\infty$?

This would directly imply Dirichlet's theorem on primes in arithmetic progressions if we make use of this
Let $a_n$ be a sequence of natural numbers, strictly increasing with $\gcd(a_i,a_j)=1$.
Then if $\sum\limits_{n=1}^\infty\frac{1}{a_n}=+\infty$ then the sequence contains infinitely many prime numbers.

I tried to modify some proofs which show the divergence of $\sum\frac{1}{p}$ but without much success.
Thank you very much in advance!

EDIT: The primes are distinct and the residue classes are not reduced modulo $p$.Suppose we start with the primes $2,3,7$ and their residue classes are $(1)_2 , (2)_3 , (4)_7$ which means $r_1=1$, $r_2=2$ and $r_3=4$. The least number not covered by the progressions $1+2k , 2+3k , 4+7k$ is $6$.We define then $r_4=6$ and $6$ is going to be a new residue class for a new prime (random choice) let's say $p_4=17$.Then $r_5=10$ and we choose a new prime (Let's say $p_5=5$) and continue in this direction.
The $r_i$'s could be much greater than the $p_i$'s

  • 2
    $\begingroup$ How do you choose those "random" primes? Do you want this result to hold for each possible way to choose them? Are you assuming that each prime will be chosen eventually? $\endgroup$ Jan 2, 2015 at 0:10
  • 2
    $\begingroup$ @S.Carnahan: in his first comment, KG says the case $\sum\frac{1}{p_n}<+\infty$ is easy. If $\sum\frac{1}{p_n}=+\infty$ and $r_n\le p_n$ for all $n$, then also $\sum\frac{1}{r_n}=+\infty$. So I guess the case of interest is when many $r_n$ are possibly larger than $p_n$. $\endgroup$ Jan 2, 2015 at 9:29
  • 3
    $\begingroup$ Don't know how to prove your claim, but I like the lemma... $\endgroup$
    – Seva
    Jan 2, 2015 at 11:43
  • 2
    $\begingroup$ @Seva I was undergarduate when I proved it and I was sure it could have many applications,but I have not found anything nice so far.Thank you very much! $\endgroup$ Jan 2, 2015 at 12:11
  • 3
    $\begingroup$ I guess if $(a_j)_j$ are pairwise relatively prime and only contain $n$ primes, then $\sum_j1/a_j\le 1+ \sum_{j=1}^n 1/p_j + \sum_{j=1}^\infty 1/p_j^2<+\infty$ $\endgroup$ Jan 2, 2015 at 19:59

1 Answer 1


The question makes sense if the $r$'s are all positive. The answer is likely to be yes for the folllowing reason: if it were no, there would be an explicit sequence where the $r$'s grow faster than $O(1/f'(n))$, where $f(n)$ is smaller than any iterated $\log$ function, and thus smaller than $\log \log\log\log\log n$, call this $\log_5 n$ or $g(n)$. Current lower bounds of the conceivable maximal growth rate of the $r$'s are like $$\dfrac1{g'(n)(\log_3 n)^2},$$ see recent work of Ford, Konyagin, Green, Maynard, and Tao. Having such a sequence of $r$'s and $p$'s would allow one to radically improve on this bound, for one could leverage this to find really large gaps between primes.

Of related interest may be Kanolds work in 1963-65 on such sequences of $r$'s. If the $r$'s grow slowly enough (something like $n^{2-c}$), one can get Linnik's theorem on the least prime in arithmetic progressions as well as a non-quantitative version of Dirichlet's Theorem through elementary means.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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