IMO 2016 · Problem 4

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 value of the positive integer \(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?

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{6} \]

Solution

We first determine which primes can divide two nearby values of \(P\).

Suppose a prime \(p\) divides both \(P(n)\) and \(P(n+d)\), where \(d\ge1\). Since every value of \(P\) is odd, \(p\) is odd. Moreover, \[ P(n+d)-P(n)=d(2n+d+1). \] Thus either \(p\mid d\), or \(2n+1\equiv-d\pmod p\). In the latter case, \[ 0\equiv4P(n)=(2n+1)^2+3\equiv d^2+3\pmod p. \] Consequently, \[ p\mid d(d^2+3). \] In particular:

  • Consecutive values \(P(n)\) and \(P(n+1)\) are coprime, since \(p\) would have to be an odd prime dividing \(4\).
  • Values two places apart can share only the prime \(7\), since \(p\mid14\).
  • Values three places apart can share only the prime \(3\), since \(p\mid36\).

Now write \(Q_i=P(a+i)\). These values are distinct because \(P(n+1)-P(n)=2n+2>0\) for \(n\ge1\).

We show that \(b\le5\) is impossible.

If \(b=1\), the set has too few elements. If \(b=2\), its elements are coprime. If \(b=3\), the middle element \(Q_2\) is coprime to both other elements.

If \(b=4\), the only possible partner for \(Q_2\) is \(Q_4\), so \(7\mid Q_2\). Likewise, the only possible partner for \(Q_3\) is \(Q_1\), so \(7\mid Q_3\). This contradicts the coprimality of consecutive values \(Q_2\) and \(Q_3\).

Finally, suppose \(b=5\). The middle element \(Q_3\) can share a prime factor only with \(Q_1\) or \(Q_5\), both two places away. Hence \(7\mid Q_3\). Because \(Q_2\) and \(Q_4\) are each coprime to \(Q_3\), neither is divisible by \(7\).

The element \(Q_2\) cannot share a prime factor with its neighbours \(Q_1,Q_3\), nor with \(Q_4\), since that would require divisibility by \(7\). Its partner must therefore be \(Q_5\), giving \(3\mid Q_2\). Similarly, \(Q_4\) must have \(Q_1\) as a partner, giving \(3\mid Q_4\). But \(Q_2\) and \(Q_4\) are two places apart, so their only possible common prime is \(7\), a contradiction.

Thus \(b\ge6\).

To attain \(b=6\), take \(a=195\). The six values can be paired as follows: \[ \begin{aligned} P(196)&=3\cdot12871, & P(199)&=3\cdot13267,\\ P(197)&=19\cdot2053, & P(201)&=19\cdot2137,\\ P(198)&=7\cdot5629, & P(200)&=7\cdot5743. \end{aligned} \] Every element therefore shares a prime factor with another element, so this set is fragrant. The least possible value is \(\boxed{6}\).

The solution was checked against the official IMO shortlist solutions.