$(\text{a})$ Do there exist 14 consecutive positive integers each of which is divisible by one or more primes $p$ from the interval $2\le p \le 11$? $(\text{b})$ Do there exist 21 consecutive positive integers each of which is divisible by one or more primes $p$ from the interval $2\le p \le 13$?
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, inequalities, blogs, number theory unsolved, number theory
17.08.2011 00:18
EDIT: Wow, how stupid can I get? Just listen to professordad.
17.08.2011 00:39
5/4 : Possibly using or with help from http://mks.mff.cuni.cz/kalva/usa/usoln/usol861.html
17.08.2011 00:41
@professordad, if you see my solution, then part 1 should be possible... am I missing something?
17.08.2011 00:43
The question statement for the first part asked for primes less than $13$, which implies a strict inequality; therefore $15!+13$ does not fit the criteria, as it is not divisible by $2, 3, 5, 7$ (you interpreted it as all primes less than or equal to $13$). Edit: Beaten
03.12.2013 06:43
Here's a blog post on this problem that I wrote. [If you visit before 12/3/2013 there will be nothing, since I haven't had time to actually write the sol.]
05.03.2017 22:24
As always, OEIS is relevant.
20.10.2021 00:45
Solution for (b):
Any errors, just let me know!
08.12.2022 16:09
Perceval wrote: Solution for (b):
Any errors, just let me know! It seems numbers $x+1, x+11, x+13, x+17, x+19$ are not divisible by any of those prime numbers.
30.12.2023 09:59
Here’s a real solution: 1. No. Suppose, for the sake of contradiction that there do exist $14$ consecutive numbers. Then, there are $7$ odd numbers---let them be $n$, $n + 2$, $n + 4$, $n + 6$, $n + 8$, $n + 10$, and $n + 12$. Multiples of $5$, $7$, and $11$ among these $7$ numbers must be separated by at least $10$, $14$, and $22$ respectively. Thus, there are at most two multiples of $5$, one multiple of $7$, and one multiple of $11$. Thus, the remaining three numbers must all be multiples of $3$, and separated by $6$. The only way this is possible is if $n$, $n + 6$, and $n + 12$ are multiples of $3$. However, once these numbers are chosen to be multiples of $3$, it's impossible for two of $n + 2$, $n + 4$, $n + 6$, and $n + 8$ to be multiples of five. Thus, overlap is inevitable and there does not exist $14$ consecutive numbers that satisfy the property. 2. Yes. By the Chinese Remainder Theorem, there exists an integer $n$ such that \begin{align*} n &\equiv 1 \pmod{2} & n &\equiv 1 \pmod{3} \\ n &\equiv -1 \pmod{5} & n &\equiv 3 \pmod{7} \\ n &\equiv 1 \pmod{11} & n &\equiv 1 \pmod{13}. \end{align*}Then, the integers $n + 1, n + 2, \ldots, n + 21$ satisfy the condition. Explicitly, \begin{align*} 5 &\mid (n + 1) & 3 &\mid (n + 2) & 2 &\mid (n + 3) & 7 &\mid (n + 4) & 3 &\mid (n + 5) \\ 5 &\mid (n + 6) & 2 &\mid (n + 7) & 3 &\mid (n + 8) & 2 &\mid (n + 9) & 11 &\mid (n + 10) \\ 5 &\mid (n + 11) & 13 &\mid (n + 12) & 2 &\mid (n + 13) & 3 &\mid (n + 14) & 2 &\mid (n + 15) \\ 5 &\mid (n + 16) & 3 &\mid (n + 17) & 7 &\mid (n + 18) & 2 &\mid (n + 19) & 3 &\mid (n + 20) \\ 5 &\mid (n + 21). \end{align*}One can also explicitly calculate $n = 9439$ as a possible value. How to come up with this solution? Just write down $21$ circles, and cross out every multiple of $2, 3, \ldots, 13$ while trying to avoid overlap. Or in other words, just do it.