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 smallest possible value of a positive integer

b

such that there exists a non-negative integer

a

for which the set

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

is fragrant?

Step 1 of 5: Four sharp Euclidean-algorithm bounds

Previous step Next step

In plain words

Since $P(n+d)-P(n)$ is a simple polynomial in $n$ and $d$ , running the Euclidean algorithm on $P(n)$ and this difference pins down the gcd to a small fixed divisor depending only on $d$ .

\gcd(P(n),P(n{+}1))=1,\ \ \gcd(P(n),P(n{+}2))\mid7,\ \ \gcd(P(n),P(n{+}3))\mid3,\ \ \gcd(P(n),P(n{+}4))\mid19

Detailed analysis

Since $P(n)=n^2+n+1$ , one computes $P(n+d)-P(n)=d(2n+d+1)$ for each gap $d$ . Running the Euclidean algorithm (eliminating $n$ using $P(n)\equiv0$ ) shows $\gcd(P(n),P(n+1))=1$ , $\gcd(P(n),P(n+2))\mid7$ , $\gcd(P(n),P(n+3))\mid3$ , and $\gcd(P(n),P(n+4))\mid19$ , for all integers $n$ .