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 4 of 5: Building

b=6

with the Chinese Remainder Theorem

Previous step Next step

In plain words

Choosing $a$ so that three specific pairs among $\{a+1,\dots,a+6\}$ each hit the required residues realizes exactly one gap- $2$ , one gap- $3$ , and one gap- $4$ coincidence, this time enough to cover all six vertices in a valid pairing.

a{+}1\equiv7,\ a{+}5\equiv11\!\!\pmod{19};\quad a{+}2\equiv2,\ a{+}4\equiv4\!\!\pmod7;\quad a{+}3\equiv1,\ a{+}6\equiv1\!\!\pmod3

Detailed analysis

By the Chinese Remainder Theorem, choose $a$ (there are infinitely many, by CRT applied to the pairwise coprime moduli $3,7,19$ ) so that simultaneously $a+1\equiv7\pmod{19}$ and $a+5\equiv11\pmod{19}$ (making $19\mid\gcd(P(a+1),P(a+5))$ , a gap- $4$ pair), $a+2\equiv2\pmod7$ and $a+4\equiv4\pmod7$ (making $7\mid\gcd(P(a+2),P(a+4))$ , a gap- $2$ pair), and $a+3\equiv1\pmod3$ and $a+6\equiv1\pmod3$ (making $3\mid\gcd(P(a+3),P(a+6))$ , a gap- $3$ pair).