After deleting the multiples of $2$ and multiples of $3$ from list of integers from $1$ to $N$, why are a fifth of the numbers still multiples of 5?

Question

I was reading an explanation about there being infinitely many primes that started off like this:

Say to the contrary there are finitely many and $p$ is the largest prime. Then let $N$ be the product of all the primes, so $N=2\times3\times5\times7\times\ldots\times p$.

Of the numbers in the list $1,2,3,4,5,\ldots,N-2,N-1,N$, half of them are divisible by $2$. We cross those numbers off the list, and we have $1,3,5,7,9$ and so on. Then of those numbers in this list, a third of them are multiples of $3$.

At first I thought the spacing of the numbers would make it so that not every 3 consecutive numbers in the list would have exactly 1 multiple of 3, but I reasoned that every 3 consecutive odd numbers $2n+1,2n+3,2n+5$ must have a multiple of 3 because $2n+1$ is either $\equiv0,1$ or $2\pmod3$.

Okay, then from this list of only odd numbers, we delete all the multiples of $3$, which I now believe is a third of the numbers.

Then the book claims that of this new list (with all multiples of $2$ and all multiples $3$ crossed out), exactly a fifth of them are multiples of $5$. Now I am stuck as to why exactly a fifth of these numbers are multiples of 5. I understand that a fifth of the numbers from the original list $1,2,3,\ldots, N$ are multiples of $5$, but it seemed to me that the uneven spacing of this list, with the multiples of $2$ and $3$ deleted, might make it so that we aren't guaranteed a multiple of $5$ every five consecutive numbers anymore. How do we know a fifth of the numbers in the new list are multiples of $5$? (The explanation goes on to do this with all the primes until $p$.)

Answer 1

Think of the pattern of numbers modulo $30$ (we choose $30$ because $30=2\times3\times5$).

After removing multiples of $2$ and $3$ you are left with

$30n+1$, $30n+5$, $30n+7$, $30n+11$, $30n+13$, $30n+17$, $30n+19$, $30n+23$, $30n+25$, $30n+29$

Of these $10$ numbers just $2$ are multiples of 5 - the second one $30n+5$ and the ninth one $30n+25$. Since this pattern repeats, one fifth of the remaining numbers are multiples of 5, even though they are not evenly spaced among the remaining numbers.

Answer 2

Does the book place any requirements on $N$? Let's say $N = 30$. Then, after crossing out the nontrivial multiples of $2$ and $3$, we have:

$$\require{cancel} \begin{eqnarray} 1 & 2 & 3 & \cancel{4} & 5 & \cancel{6} & 7 & \cancel{8} & \cancel{9} & \cancel{10} \\ 11 & \cancel{12} & 13 & \cancel{14} & \cancel{15} & \cancel{16} & 17 & \cancel{18} & 19 & \cancel{20} \\ \cancel{21} & \cancel{22} & 23 & \cancel{24} & 25 & \cancel{26} & \cancel{27} & \cancel{28} & 29 & \cancel{30} \\ \end{eqnarray}$$

Ignore $1$ for the moment. The numbers that are not crossed out at this stage are $2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29$. So $10$ is already crossed out on account of being a multiple of $2$, as is $20$, while $15$ is crossed out on account of being a multiple of $3$.

We have eleven numbers out of thirty not crossed out. Two of them are multiples of $5$, namely $25$ and $5$ itself. Two out of eleven is not exactly one fifth but it is close. We can make that ratio smaller if we take $N$ up to $34$ and cross out $32, 33, 34$.