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

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

Page

Toolbox

Search

2016 IMO Problems/Problem 4

Problem

Solution

See Also