$(\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
pie8.539734222
17.08.2011 00:18
For the first part, if we look at the numbers following $15!$, we find
$15!+2$ is divisible by $2$
$15!+3$ is divisible by $3$
$15!+4$ is divisible by $4$ (and also $2$)
and so on until
$15!+15$ is divisible by $15$ (and also $3$ and $5$)
The highest prime divisor is of
$15!+13$, which is divisible by $13$.
So now we have $14$ numbers, each divisible by a prime less than $13$.
EDIT: Wow, how stupid can I get? Just listen to professordad.
professordad
17.08.2011 00:39
First part:
We seek to spread the divisors out as evenly as possible. Exactly 7 numbers will be even. Now let the odd numbers be A, B, C, D, E, F, and G. Note that we could have A, D, and G all divisible by 3, but then at least one of A or G must be divisible by 5. Or we could have B and E divisible by 3, and A and F divisible by 5. (The other arrangements don't work, either because there is only one 5 in the range, or only three numbers are divisible by 3 or 5.) Thus we have at most 4 numbers divisible by either 3 or 5. There are 4 other numbers with only 3 other divisors, so no.
Second part:
Here, we maximize the even numbers, so now we have 10 odd numbers. Label these as A, B, C, D, E, F, G, H, I, and J. We realize that making A, D, G, and J divisible by 3, and making C and H divisible by 5 spreads the divisors out most evenly (there can be at most 4 numbers divisible by 3 and at most 2 numbers divisible by 5 in this range). Furthermore, we can make B and I divisible by 7. Now we have two spots left, so we can put either 11 or 13 in these.
For solid evidence, WLOG assume that 11|F and 13|G. Then, making A be 3 mod 143 satisfies this. Also, A is 3 mod 2 and 3 mod 3, so it is 3 mod 858. A is also 5 mod 7 and 1 mod 5. For the sake of calculation, we do 5 mod 7 first; after some calculations (861, 1719, 2577, 3435) we find 3435 mod 6006 satisfies the mod 7 condition, and (9441 wow) 9441 mod 30030 satisfies the mod 5 condition. So 9440, 9441, etc to 9460 should work. (And I tested it and found it works...)
5/4 : Possibly using or with help from http://mks.mff.cuni.cz/kalva/usa/usoln/usol861.html
Is 13 less than 13?
pie8.539734222
17.08.2011 00:41
@professordad, if you see my solution, then part 1 should be possible... am I missing something?
GlassBead
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
MSTang
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.]
rafayaashary1
05.03.2017 22:24
As always, OEIS is relevant.
Perceval
20.10.2021 00:45
Solution for (b):
By the Chinese Remainder Theorem, there exists an integer x such that
$x \equiv 0 \pmod {2\cdot3\cdot5\cdot7} \\
x \equiv 2 \pmod {11} \\
x \equiv 2 \pmod {13} $
It's easy to see that the sequence x, x+1, x+2, ... , x+20 has the desired property.
Any errors, just let me know!
Arslan
08.12.2022 16:09
Perceval wrote: Solution for (b):
By the Chinese Remainder Theorem, there exists an integer x such that
$x \equiv 0 \pmod {2\cdot3\cdot5\cdot7} \\
x \equiv 2 \pmod {11} \\
x \equiv 2 \pmod {13} $
It's easy to see that the sequence x, x+1, x+2, ... , x+20 has the desired property.
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.
solasky
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.