6
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand now, thank you very much. The book claims in general, $\frac{1}{p}$ of the numbers left after we've crossed out 2,3, etc are multiples of $p$. I guess we have to find the largest $k$ such that $p^{k}\le2.3\ldots p$. (So in this case it's 2, but I don't know in general how to find that.) Then we divide $k$ by the number of numbers from 0 to $p$ which are left after we've done all the crossing out. (So in this case it's 10, and in general, I only have an idea using inclusion-exclusion.) Then I guess we somehow end up with $\frac{1}{p}$. $\endgroup$ – anonanon444 Jul 11 '18 at 22:09
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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