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$.)
Best Answer
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.