(IMO 2016 P4) A set of natural numbers is said to be fragrant if it contains at least two elements and if 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$. Determine the smallest positive integer $b$ for which there exists a positive integer $a$ such that the set

$$
\{P(a+1), P(a+2), \ldots, P(a+b)\}
$$

is fragrant.
Here it is natural to think that $b$ is likely to be relatively small, otherwise the problem risks being very complicated. We quickly calculate the $P(n)$ for $n$ between 1 and 20, and factorize them into prime factors to understand a bit how the problem works. Let's look at $b=2$: the question comes down to whether $P(n)$ and $P(n+1)$ are coprime. For this, we calculate $d$ their gcd. We have $d$ which divides $P(n+1)-P(n)=n^{2}+3 n+3-n^{2}-n-1=2 n+2=2(n+1)$. Moreover, $d$ is odd because $P(n)=n(n+1)+1$ is odd, so $d$ divides $(n+1$ and $n(n+1)+1$ so $d$ divides $1, d=1$.

Now what does this allow us to say about $b$? If $b=2$, let $a$ be an integer satisfying the statement. Since $P(a+1)$ and $P(a+2)$ are coprime for any integer $a$, the set is not fragranced. We have $b \geqslant 3$. If $b=3$, let $a$ satisfy the statement, $P(a+2)$ is coprime with $P(a+1)$ and $P(a+3)$ for any integer $a$, so necessarily $b \geqslant 4$.

Now we can ask ourselves if $P(n)$ and $P(n+2)$ are coprime. Let $d$ be their gcd, then $d$ divides $P(n+2)-P(n)=4 n+4+2=2(2 n+3)$. Thus $d$ divides $2 n+3$ so since $d$ divides $(2 n)^{2}+2 \times 2 n+4, d$ divides $9-6+4=7$. Thus either $d=1$, or $d=7$ and 7 divides $2 n+3$, so 7 divides $8 n+12$, so 7 divides $n-2$. In particular, since $P(2)$ and $P(4)$ are 7 and 21 and are indeed divisible by 7, we deduce that $P(7 k+2)$ and $P(7 k+4)$ are always divisible by 7. Thus $P(n)$ and $P(n+2)$ are not coprime if and only if $n \equiv 2(\bmod 7)$.

We ask the same question for $P(n)$ and $P(n+3)$: let $d$ be their gcd, we have $d$ which divides $P(n+3)-P(n)=6 n+12$ so $d$ divides $3(n+2)$. Now $P(1)$ is divisible by $3, P(0)$ and $P(2)$ are not, so we deduce that $P(3 k+2)$ and $P(3 k)$ are not divisible by 3 and $P(3 k+1)$ is. Thus if $n \equiv 1(\bmod 3), P(n)$ and $P(n+3)$ are both divisible by 3. If $n \not \equiv 1$ ( $\bmod 3$ ), we then have $d$ which divides $n+2$ and $n^{2}+n+1$, so $d$ divides $(-2)^{2}-2+1=3$, contradiction. Thus $P(n)$ and $P(n+3)$ are coprime if and only if $n \not \equiv 1(\bmod 3)-$.

Now let's return to the problem: if $b=4$, let $a$ be an integer satisfying the statement. Since $P(a+2)$ is coprime with $P(a+3)$ and $P(a+1)$, then it is not coprime with $P(a+4)$. Similarly, $P(a+3)$ is not coprime with $P(a+1)$. We then have $a+2 \equiv a+3 \equiv 2(\bmod 7)$, contradiction. If $b=5$, let $a$ be an integer satisfying the statement.

Now let's return to the problem: suppose that $b=5$, let $a$ be an integer satisfying the statement. Since $P(a+3)$ is coprime with $P(a+2)$ and $P(a+4)$, it must necessarily not be coprime with $P(n+1)$ or $P(n+5)$, and they are both divisible by 7. In particular, $P(n+2)$ and $P(n+4)$ are not divisible by 7, so they are coprime. Necessarily $P(n+2)$ and $P(n+5)$ are not coprime, same for $P(n+1)$ and $P(n+4)$, so $n+1 \equiv n+2 \equiv 1$ $(\bmod 3)$ contradiction.

Now we can ask ourselves if $P(n)$ and $P(n+4)$ are coprime. Let $d$ be their gcd, then $d$ divides $P(n+4)-P(n)=8 n+16+4=4(2 n+5)$. Thus $d$ divides $2 n+5$ so since $d$ divides $(2 n)^{2}+2 \times 2 n+4, d$ divides $25-10+4=19$. Thus either $d=1$, or $d=7$ and 19 divides $2 n+5$, so 19 divides $20 n+50$. Thus 19 divides $n-7$. Now we notice that $P(7)$ and
$P(11)$ are divisible by 19, so $P(n)$ and $P(n+4)$ are coprime if and only if $n \not \equiv 7(\bmod 19)$.

Now let's look at $b=6$, try to pair the different $P(a+1), P(a+2), \ldots, P(a+$ 6) to have potentially non-coprime pairs: thus the difference of the arguments of $p$ must be 2, 3 or 4, but not the same thing twice. We can then pair them as follows: $\{P(a+1), P(a+4)\},\{P(a+2), P(a+6)\},\{P(a+3), P(a+5)\}$. It is enough to have $a+1 \equiv 1(\bmod 3), a+2 \equiv 7(\bmod 19)$ and $a+3 \equiv 2(\bmod 7)$ and $a$ strictly positive, which is possible via the Chinese remainder theorem, so that the 3 different sets above consist of non-coprime integers. The set is then fragranced, so $b=6$ is the minimum value satisfying the statement.