Eratosthenes-like sieves will always leave an infinite set of unsieved numbers

Question

In this question I visualized the sieve of Eratosthenes as a series of combs whose teeth cover (i.e. eliminate) composite numbers. The $i$th comb has teeth spaced by $p_i$ and is positioned so that the first tooth covers $p_i^2$, thus covering or removing numbers of the form $p_i^2+np_i$. Collectively, this leaves only primes uncovered, which are known to comprise an infinite set.

It is possible to shift the combs that are used in my visualization, so that the first number each one covers is not $p_i^2$, but $r_i$, where $0<r_i \le p_i-1$. I wish to argue here that no how many such shifts are performed, an infinite set of numbers remain uncovered.

My questions are general: First, is my reasoning sound, or have I gone astray at some point? Second, is either the result, or my line of reasoning to the result, already known? If so, citations or references would be appreciated. Finally, although I can state my result in mathematical terms, my arguments are made in words, and I wonder whether a tighter mathematical statement of the argument is possible?

I begin with an axiom, because it seems ineluctably true, but I don't see a way to prove it. The axiom is: If there is an arrangement of combs that cover all but a finite number of numbers, that arrangement can be arrived at starting with the arrangement in the standard sieve of Eratosthenes and shifting one comb at a time until the final arrangement is reached. This axiom allows me to start my argument with the arrangement as it exists in the standard sieve of Eratosthenes.

From that starting arrangement, move the comb corresponding to $p_a$ to the starting point $r_a$. This now covers numbers of the form $r_a+np_a$. Pursuant to Dirichlet's theorem, an infinite number of primes that were previously uncovered will be covered after such a shift. On the other hand, an infinite set of numbers of the form $p_a^k$ will be uncovered, so shifting any one comb still leaves an infinite number of numbers uncovered.

Next, shift the comb corresponding to $p_b$ to start at $r_b$. Note that there is no requirement that $r_b \ne r_a$. An infinite number of primes of the form $r_b+np_b$ will be covered, but numbers of the form $p_b^j$ will be uncovered. Now we have to contend with the possibility that some of the numbers $p_a^k$ might be covered by $r_b+np_b$, and some of the numbers $p_b^j$ might be covered by $r_a+np_a$, and this phenomenon might conceivably (with enough shifts) cover all of numbers that are powers of primes. But this second shift also uncovers another infinite set of numbers, those of the form $p_a^kp_b^j$.

The argument then goes that no matter how many shifts are made, no matter how many numbers are covered as a result of the shift, an infinite number of previously covered numbers are simultaneously uncovered. For $m$ independent shifts, the necessarily uncovered numbers will generally be expressible as $\prod_i(p_{i\in m}^{k_i})$, and will be infinite in number. Hence, no number of shifts will result in an arrangement of combs able to cover all but a finite set of numbers.

I can state the result mathematically: If $K_i=\{r_i+np_i\}$, then $|\mathbb N-\cup_i(K_i)|=\infty$. But have I proved it?

Answer 1

When you write, "no how many such shifts are performed," I take that as permitting an infinite number of shifts. So, let the prime $2$ cover $1,3,5,7,\dots$; let $3$ cover $2,5,8,11,\dots$; the smallest uncovered nummber is $4$, so let $5$ cover $4,9,14,19,\dots$; the smallest uncovered number is $6$, so let $7$ cover $6,13,20,27,\dots$; let $11$ cover $10,21,32,43,\dots$; and so on. Every number gets covered.

Answer 2

It is plain that if you have an infinite set of combs, each with a distinct prime spacing of teeth, you can cover the entire number line (with the single exception of $1$) by placing the initial tooth of each comb on its corresponding prime number. Since every number greater than $1$ has a prime factorization, every such number will be covered by at least one tooth of some comb. To obtain the sieve of Eratosthenes, we add a rule to this, that the first covered number for any particular comb is not $p_i$, but $2p_i$. This leaves uncovered an infinite set of numbers, the primes. Another way of thinking of this arrangement is that each comb covers numbers greater than $p_i$ that are $\equiv 0 \bmod p_i$

My question asked if we used a different rule, that combs for any particular $p_i$ may not cover numbers $\equiv 0 \bmod p_i$, would that leave an infinite number of numbers uncovered?

Gerry Myerson's answer provided a method to use the set of combs, abide by my new rule, and still cover the entire number line.

My issue came down to this line of thinking: Use of the $2$ comb leaves uncovered numbers of the form $2^a$. Then use of the $3$ comb leaves uncovered numbers of the form $2^a3^b$. Repeating the argument further, one obtains in serial fashion infinite sets of numbers of the form $2^a3^b5^c7^d\dots$ that are not covered.

I now see that numbers in these sets can also be characterized as numbers that are $\equiv 0 \bmod p_i$ for all $i\le n$. But as $n \rightarrow \infty$, such numbers cannot exist. Suppose such a number $K$ did exist. Then by the Euclidean proof of the infinite number of primes, $K+1$ would have larger prime factors, contradicting the assumption that $n \rightarrow \infty$ was valid in a meaningful way. Just as Gerry Myerson stated, my hypothetical numbers would eventually get swallowed up in the infinite application of successive combs.