Prove that for no integer $k \ge 2$, between $10k$ and $10k + 100$ there are more than $23$ prime numbers.
Problem
Source: Germany Federal - Bundeswettbewerb Mathematik 2019 round 2, p4
Tags: number theory, primes
16.06.2021 20:58
Note that $lcm(2, 3, 5, 7) = 210$. Let $T$ be the set of positive integers that are not divisible by any of $2, 3, 5$ or $7$. Let $R_0, R_1, \ldots, R_{20}$ be sets such that $R_i$ is the set of integers in $[10i, 10i + 9]$ that are not divisible by any of $2, 3, 5$ or $7$. We let $R_i = R_{i+21}$. Let $S_i = R_i \cup R_{i+1} \cup \ldots \cup R_{i+9}$. Note that the number of primes in $[10i, 10i + 100]$ is at most $|S_i|$. We see that $$T = \{1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199\}$$ From this, we get the values of $|R_i|$ and $|S_i|$ as follows: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\\hline |R_i| & 1 & 4 & 2 & 2 & 3 & 2 & 2 & 3 & 2 & 1 & 4 & 1 & 2 & 3 & 2 & 2 & 3 & 2 & 2 & 4 & 1 \\\hline |S_i| & 22 & 25 & 22 & 22 & 23 & 22 & 22 & 23 & 22 & 22 & 25 & 22 & 22 & 24 & 23 & 23 & 24 & 23 & 23 & 24 & 22 \\\hline \end{array}$$ If $|S_i| \leq 23$, then there are at most $23$ prime numbers in $[10i, 10i + 100]$. For nonnegative integers $k$, note that $|S_i| = 24$ for $i = 21k + 13, 21k + 16, 21k + 19$ and $|S_i| = 25$ for $i = 21k + 1, 21k + 10$. Thus, for $i = 13, 16, 19$, we need to show that one element in $S_i$ is not prime, and for $i = 1, 10$, we need to show that two elements in $S_i$ are not prime. For $i = 21k + 13$ and $i = 21k + 16$, note that $[210k + 130, 210k + 230]$ and $[210k + 160, 210k + 260]$ both contain $[210k + 160, 210k + 230]$. Some elements of $T$ in $[210k + 160, 210k + 230]$ are $210k + 173, 210k + 181, 210k + 191, 210k + 193, 210k + 197, 210k + 199, 210k + 209, 210k + 211, 210k + 223, 210k + 227, 210k + 229$. Note that they cover all residues $\pmod{11}$. Therefore, at least one of them is divisible by $11$ and is not prime. For $i = 21k + 19$, note that $210k + 191, 210k + 193, 210k + 197, 210k + 199, 210k + 209, 210k + 211, 210k + 223, 210k + 227, 210k + 229, 210k + 239, 210k + 247$ are all in $T$ and $[210k + 190, 210k + 290]$, and cover all residues $\pmod{11}$. Therefore, at least one of them is divisible by $11$ and is not prime. For $i = 21k + 1$, note that $210k + 11, 210k + 23, 210k + 29, 210k + 31, 210k + 37, 210k + 41, 210k + 43, 210k + 47, 210k + 71, 210k + 79, 210k + 83$ are all in $T$ and $[210k + 10, 210k + 110]$, and cover all residues $\pmod{11}$. Also, note that $210k + 13, 210k + 17, 210k + 19, 210k + 53, 210k + 59, 210k + 61, 210k + 67, 210k + 73, 210k + 89, 210k + 101, 210k + 103, 210k + 107, 210k + 109$ are all in $T$ and $[210k + 10, 210k + 110]$, and cover all residues $\pmod{13}$. Since the aforementioned $24$ numbers are distinct, at least one of the elements in $T \cap [210k + 10, 210k + 110]$ is divisible by $11$ and another one is divisible by $13$, giving $2$ composite numbers. For $i = 21k + 10$, note that $210k + 117, 210k + 121, 210k + 129, 210k + 163, 210k + 167, 210k + 169, 210k + 173, 210k + 179, 210k + 181, 210k + 187, 210k + 199$ are all in $T$ and $[210k + 100, 210k + 200]$, and cover all residues $\pmod{11}$. Also, note that $210k + 101, 210k + 103, 210k + 107, 210k + 109, 210k + 121, 210k + 137, 210k + 143, 210k + 149, 210k + 151, 210k + 157, 210k + 191, 210k + 193, 210k + 197$ are all in $T$ and $[210k + 100, 210k + 200]$, and cover all residues $\pmod{13}$. Since the aforementioned $24$ numbers are distinct, at least one of the elements in $T \cap [210k + 100, 210k + 200]$ is divisible by $11$ and another one is divisible by $13$, giving $2$ composite numbers. Therefore, for all integers $k \geq 2$, there are at most $23$ prime numbers between $10k$ and $10k + 100$.