2016 IMO Problems/Problem 4

Problem

A set of positive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let $P(n)=n^2+n+1$. What is the least possible positive integer value of $b$ such that there exists a non-negative integer $a$ for which the set $\{P(a+1),P(a+2),\ldots,P(a+b)\}$ is fragrant?

Solution

Consider $P(x)$ and $P(x+y)$. We note that in order to $p \mid P(x)$ and $p \mid P(x+y)-P(x)$ we must have $p \mid x^2+x+1$ and $p \mid y(2x+y+1)$. It is obvious that $p \equiv 1 \pmod{6}$ since $p \mid n^2+n+1 \mid (2n+1)^2+3$ or $\left( \tfrac{-3}{p} \right)=1$.

If $y=1$ then $p \mid 2x+2$ implies $p \mid x+1$. WLOG, we can let $x=p-1$ and see that $p \nmid x^2+x+1$. So there doesn't exists $x$ so that $\gcd \left( P(x),P(x+1) \right)>1$.

If $y=2$, we find $p \mid 2x+3$ and we let $x=\tfrac{p-3}{2}$. Hence, from $p \mid x^2+x+1$ we get $p=7$. So there is one prime $p=7$ such that $\gcd \left( P(x),P(x+2) \right)>1$.

If $y=3$, it is obvious that $p=3$ satisfy and is the only answer.

If $y=4$, we do the similar thing and get $p \mid 2x+5$ and $p \mid x^2+x+1$ so $p=19$. ___________________________ Now, back to the problem, since there doesn't exists any prime $p$ for $y=1$ so $b \ge 3$. The only prime for $y=2$ is $p=7$ so if we choose $7 \mid P(x+1), 7 \mid P(x+3)$ then there will be a number $7 \nmid P(x+2)$ remains. This means $b \ge 5$ since we need a prime $p \mid P(x+2)$ and $p \mid P(x+y)$ but $y \ge 5$ since $p \ne 7$.

If $b=5$, we consider two cases, where there are two numbers that are divisible by $19$ (which means $19 \mid P(x+1), 19 \mid P(x+5)$), the middle-three numbers $P(x+2),P(x+3),P(x+4)$ we can't find a way make each two of them have common prime factor. If no two are divisible by $19$ then they can only be divisible by $7,3$, but it can't cover all $5$ "consecutive" numbers.

If $b=6$ then we can pick $19 \mid P(x+2),P(x+6), 3 \mid P(x+1), P(x+4), 7 \mid P(x+3), 7 \mid P(x+5)$.

So the final answer is $b=6$.

See Also

2016 IMO (Problems) • Resources
Preceded by
Problem 3
1 2 3 4 5 6 Followed by
Problem 5
All IMO Problems and Solutions