The minimum of $b$ is 6. $a=196,b=6$ satisfy all the conditions

The answer is $b = 6$. First, we prove $b \ge 6$ must hold. It is not hard to prove the following divisibilities by Euclid: \begin{align*} \gcd(P(n), P(n+1)) &\mid 1 \\ \gcd(P(n), P(n+2)) &\mid 7 \\ \gcd(P(n), P(n+3)) &\mid 3 \\ \gcd(P(n), P(n+4)) &\mid 19. \end{align*}Now assume for contradiction $b \le 5$. Then any GCD's among $P(a+1)$, ..., $P(a+b)$ must be among $\{3, 7, 19\}$. Consider a multi-graph on $\{a+1, \dots, a+b\}$ where we join two elements with nontrivial GCD and label the edge with the corresponding prime. Then we readily see there is at most one edge each of $\{3, 7, 19\}$: id est at most one edge of gap $2$, $3$, $4$ (and no edges of gap $1$). (By the gap of an edge $e=\{u,v\}$ we mean $|u-v|$.) But one can see (by checking the cases manually) that it's now impossible for every vertex to have nonzero degree, contradiction. To construct $b = 6$ we use the Chinese remainder theorem: select $a$ with \begin{align*} a+1 & \equiv 7 \pmod{19} \\ a+5 & \equiv 11 \pmod{19} \\ a+2 & \equiv 2 \pmod{7} \\ a+4 & \equiv 4 \pmod{7} \\ a+3 & \equiv 1 \pmod{3} \\ a+6 & \equiv 1 \pmod{3} \end{align*}which does the trick. Instructive problem, but quite routine in my opinion.

a=195 should also work

We prove $b \ge 6$ is needed. Construction for $b=6$ is $a=196$.

Now assume the contrary and say $b \le 5$. We have $$gcd(P(n),P(n+1))=1$$$$gcd(P(n),P(n+2))=7 \text{ iff } n \equiv 2 \pmod{7}$$$$gcd(P(n),P(n+3))=3 \text{ iff } n \equiv 1 \pmod{3}$$$$gcd(P(n),P(n+4)) = 19 \text{ iff } n \equiv 7 \pmod{19}$$Where equality signs can be changed with $\mid$ for all $n$. Note that the same not-equal-to-1 gcd cannot be used by our modular restrictions mentioned above. Let's use the connecting argument similar to the above. Let's assume that $a+1$ and $a+5$ are connected. This doesn't hurt at all since it is the only possible case of gcd=19 and we can CRT everything at the end. Now we have to connect $a+2,a+3,a+4$ with distances $2, 3$. If there are no edges between $a+2, a+3, a+4$, by Pigeonhole, two edges out of the three edges involving $a+2, a+3, a+4$ must have the same gcd. Contradiction. Therefore we must connect $a+2$ and $a+4$, which means that distance $2$ is used. We are left with $a+3$, but every distance from $a+3$ is either 1 or 2, so we are doomed. $\blacksquare$

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

Using the Extended Euclidean Algorithm one can see that $(P(a),P(a+1)) = 1$, $(P(a),P(a+2)) = 1,7$, $(P(a),P(a+2)) = 1,3$, $(P(a),P(a+1)) = 1,19$. Assume such set is fragnant for some $a$ and $b$, then as the GCD are primes we can split the set in partitions (in equivalence classes). This easily discard the cases up to b=5, as $(P(a),P(a+2)=7 \iff a=7k+2$ and so on for the other cases. To generate a configuration for $b=6$, one can take $(P(a+1),P(a+4))=3, (P(a+3),P(a+5))=7, (P(a+2),P(a+6))=19$ and solve the congruence relations using CRT to get $a=399t + 195$

My solution : If $b=6$, we choose $a \equiv 0 (mod$ $7)$, $a \equiv 1 (mod$ $3)$ and $a \equiv 6(mod$ $19)$ If $b \leq 5$ If $P(n+2)$ and $P(n)$ have common prime divisor so that is $7$ and $ n\equiv 2,4 (mod$ $7)$ If $P(n+3)$ and $P(n)$ have common prime divisor so that is $3$ and $ n\equiv 1(mod$ $3)$ Now we consider $P(a+1),...,P(a+5)$, we connect two of them if they have common prime divisor . So there exist $n$ such that $a+1 \leq n \leq a+5$ and $n$ , $n+3$ is connected because if it's not, there will exist 2 numbers $x,y$ such that $a+1 \leq x,y \leq a+5$ such that $P(x) \rightarrow P(x+2) ; P(y) \rightarrow P(y+2)$ then $x\equiv y (mod$ $7)$ which is impossible Obvious that $P(a+3) \rightarrow P(a+1)$ or $P(a+5)$ If $P(a+3) \rightarrow P(a+1)$ $\implies P(a+2) \rightarrow P(a+5), P(a+4) \rightarrow P(a+1)$ then $a+2 \equiv a+4(mod$ $3)$ which is impossible Then $b$ cannot smaller than $6$

What about P(n)=n?

Solution: Lemma: If $x \equiv n, n^2 \pmod {P(n)}$, then $P(x) \equiv 0 \pmod {P(n)}$. Proof: If $x \equiv n \pmod {P(n)}$ this is obviously true. If $x \equiv n^2 \pmod {P(n)}$ then \[P(x) = n^4 + n^2 + 1 = (n^4+n^3+n^2) - (n^3+n^2+n) + (n^2+n+1) \equiv 0 \pmod { n^2+n+1} \equiv 0 \pmod {P(n)}.\] Thus \[n \equiv 1 \pmod {3} \implies P(n) \equiv 0 \pmod {3}\]\[n \equiv 2,4 \pmod {7} \implies P(n) \equiv 0 \pmod {7}\]\[n \equiv 3,9 \pmod {13} \implies P(n) \equiv 0 \pmod {13}\]\[\cdots\]\[n \equiv 7,49 \pmod {57} \implies P(n) \equiv 0 \pmod {57} \text{ or } n \equiv 7,11 \pmod {19} \implies P(n) \equiv 0 \pmod {19}\]. Now it is easy to see we can have $6$ consecutive $P(n)$ such that they are $n \equiv 7 \pmod {19}, n+1 \equiv 2 \pmod {7}, n+2 \equiv 1 \pmod {3}, n+3 \equiv 4 \pmod {7}, n+4 \equiv 11 \pmod {19}, n+5 \equiv 1 \pmod {3}$ and the six values are fragrant. Using CRT, we see solutions exist at $a \equiv 196 \pmod {399}.$ We can use basic algebra to see there are no solutions for $b\le 5$, and we are done. The answer is $\boxed{6}$. $\blacksquare$ Comments: This was much easier than I expected, I completed this problem in 15 minutes before my teacher who made IMO in 86 and 87.

ash1374 wrote: What about P(n)=n? imho more interesting than the actual IMO problem.

bobthesmartypants wrote: ash1374 wrote: What about P(n)=n? imho more interesting than the actual IMO problem.

Thank you! I believed that it does not exist. Another question: is there exist such b for any polynomial P?

ash1374 wrote: What about P(n)=n? The 17 integers 2184, 2185, ..., 2200 work.

Thanks for the simpler construction! Unfortunately, the bound is still $b=17$.

Indeed, $b=17$ is the best we can get. $b<10$ can be done by hand, and this python program does the rest. We need only check up to $30030=2\times3\times5\times7\times11\times13$. #DON'T RUN IN BROWSER. C/P TO PYTHON IF YOU HAVE IT.def gcd(a,b): while b: a,b=b,a%b return a count=0 for b in range(10,18): for a in range(1,30031): count=0 fragrant=[i for i in range(a+1,a+b+1)] for i in fragrant: for j in fragrant: if i!=j: if gcd(i,j)>1: count+=1 break if count==b: print(fragrant)#DON'T RUN IN BROWSER. C/P TO PYTHON IF YOU HAVE IT. def gcd(a,b): while b: a,b=b,a%b return a count=0 for b in range(10,18): for a in range(1,30031): count=0 fragrant=[i for i in range(a+1,a+b+1)] for i in fragrant: for j in fragrant: if i!=j: if gcd(i,j)>1: count+=1 break if count==b: print(fragrant)RunResetPop Out /

Here is a method that gives some motivation to the bash. We claim that $\gcd(P(a),P(a+k))$ divides $k^3+3k$. Note that $P(a+k)-P(a)=2ak+k^2+k$. Therefore $$a\cdot[P(a+k)-P(a)]-2kP(a)=[(2k)a^2+(k^2+k)a]-[(2k)a^2+(2k)a+(2k)]=(k^2-k)a-2k.$$Thus this GCD divides both the expressions $C=2ak+k^2+k$ and $D=(k^2-k)a-2k$. We expand $C(k-1)$ and $2D$ and take the difference: $$C(k-1)-2D=[2k(k-1)a+k^3-k]-[2k(k-1)a-4k]=k^3+3k.$$Thus this GCD must divide $k^3+3k$. In fact, since $P(a)$ is always odd, the GCD must divide the greatest odd factor of $k^3+3k$. We can also show that $\gcd(P(a),P(a+1))=1$ using a similar, less-complicated method. How we performed the bash is, for the case $b=n$, we wrote $n$ blanks on the board, used this GCD property to label what each blank must be divisible by, and gradually showed that we could find two adjacent blanks that were divisible by the same number. This violates the fact that the GCD of $P(a)$ and $P(a+1)$ is 1. Once we found a suitable distribution of numbers for $b=6$, we all said "Chinese Remainder Theorem" and patted ourselves on the back.

Interestingly, the smallest value of $a$ that works for problem 4 is the same as the total score of the 4th placed country this year.

Forgive me, an old timer here, but "a" is non negative, are we saying it is implied in the question (or by convention) that the "prime factor" cannot be the element of the set itself? Before I think this through, would you just help me understand what is wrong with a=0 and b=4 ? i.e. P(0) = 3, P(4) = 21 :

Oh god, finally solved this one. Probably one of the first problems I've used CRT on, I'm surprised myself that I still know that theorem. (Well, not that I think about it, maybe not so much, the theorem itself is quite intuitive.) Let $i>1$ be a positive integer, then note \[ P(a+i)-P(a+1) = (2a+i+2)(i-1) \]and \[ P(a+1) \equiv P(a+i) \equiv a^2+3a+3 \pmod{2a+i+2}. \]So $\gcd \left(P(a+1),P(a+i \right)>1$ iff $\gcd \left(a^2+3a+3,2a+i+2 \right)>1$. With the Euclidean Algorithm, we easily calculate \begin{align} \gcd \left(a^2+3a+3,2a+4 \right) &= \gcd(1,a+2), \\ \gcd \left(a^2+3a+3,2a+5 \right) &= \gcd(a+6,-7), \\ \gcd \left(a^2+3a+3,2a+6 \right) &= \gcd(a+3,3), \\ \gcd \left(a^2+3a+3,2a+7 \right) &= \gcd(6-a,19) \end{align}for $i=2,3,4$. So $(1)$ implies that $\gcd{(P(a+1),P(a+2))}=1$ for all $a \in \mathbb{N}_0$. Then $(2)$ to $(4)$ implies $P(a+1)$ shares a common factor with $P(a+2),P(a+3),P(a+4)$ respectively, iff $a \equiv 1 \pmod 7$, $a \equiv 0 \pmod 3$, $a \equiv 6 \pmod {19}$. The factors they'd share would then be $7$,$3$ or $19$. With that it is easy to show that $b=1,2,3,4,5$ do not work. It is also not hard to show that $b=6$ works. We want to construct $a$, such that \begin{align*} \gcd(P(a+1),P(a+5)) &=19, \\ \gcd(P(a+2),P(a+4)) &=7, \\ \gcd(P(a+3),P(a+6)) &=3. \end{align*}So with the above observations, this yields \begin{align*} a &\equiv 6 \pmod{19}, \\ a &\equiv 0 \pmod{7}, \\ a &\equiv 1 \pmod{3}. \end{align*}But the Chinese Remainder Theorem ensures that there is one such number. Done.

The answer is $b=6$. Call a good pair $(m, n)$ a pair such that $P(m)$ and $P(n)$ share a prime factor. To see that this is achievable, take $a \equiv 1 \pmod 3$, $a \equiv 6 \pmod {19}$, and $a \equiv 0 \pmod 7$. Then we can check that $(P(a), P(a+3))$, $(P(a+1), P(a+5))$, and $(P(a+2), P(a+4))$ are all good. Now assume $b \leq 5$. Claim. [Prime Characterization] If $p \mid P(n)$ and $p \mid P(n+2)$, then $p=7$. Proof. Note that $p \mid 2(2a+3)$ or $p \mid 2a+3$ by taking the difference. Then $$\frac 74 = \left(-\frac 32\right)^2-\frac 32 + 1 \equiv 0 \pmod p$$implying $p=7$. $\blacksquare$ If $b = 5$, then WLOG $(P(a+1), P(a+3))$ is good (as opposed to $(P(a+3), P(a+5))$.) Note that for every $p$, there exists at most one good pair that shares a prime factor $p$. Thus, $(P(a+2), P(a+4))$ cannot be good, and it follows $(P(a+2), P(a+5))$ is good. But now there is no way to pair $P(a+4)$, contradiction! If $b \leq 4$, then there is no way to pair the $P(a+i)$'s into valid groups with distinct differences. Thus $b=6$ is indeed minimal.

The answer is b=6 3 | P(A) 7 | P(A+1) 13 | P(A+2) 3 | P(A+3) 7 | P(A+4) 13 | P(A+5) For values less than 6 we can take GCD and then contradict

Solved with HoRI_DA_GRe8, sanyalarnab, DistortedDragon1o4, SilverBlaze_SY. We can check that $a=195$ and $b = 6$ works as we get that the set $\left\{P(196),P(197),P(198),P(199),P(200),P(201)\right\} \equiv \left\{38613,39007,39403,39801,40201,40603\right\}$. We can check using calculator that the $1$st and $4$th term are divisible by $3$, $2$nd and $6$th term are divisible by $19$ and that the $3$rd and the $5$th term are divisible by $7$. Now we show that $\le 5$ does not work. We can case check that $b=1,2,3$ do not work. Now if $b=4$, note that we must have that $P(a+2)$ and $P(a+4)$ pair up and also that $P(a+1)$ and $P(a+3)$ pair up. This gives a contradiction $\pmod{7}$. Similarly we can also show some modular contradiction stuffs for the case $b=5$ also. The sketch of the maximum possible values of the GCDs are listed below in a table.

Claim that the answer is $6$ The roots of $n^2+n+1$ are $-\frac{1}{2} \pm \frac{\sqrt{-3}}{2}$, so the difference between the roots is $\sqrt{-3}$. Let $x$ be the value of $\sqrt{-3} \pmod p$ $x^2=-3 \pmod p$ For $p > 37$, $x$ is more than $6$ because then $p^2$ would be too small, so it does not have to be considered. For $p \le 37$, get that Mod 3: 0 is a root Mod 7: 2, 4 are roots Mod 13: 3, 9 are roots (too far apart) Mod 19: 7, 11 are roots Mod 31: 11, 20 are roots (too far apart) Mod 37: 16, 21 are roots If 37 is used, then there are at least 6 elements. So 3, 7, and 19 have to be used. 6 is achieved by a=195, b=6. 5 cannot be achieved because then the ones div 3 would not fit between the ones that div 19. So the answer is $\boxed{6}$

hi i dont know this

The answer is $6$. For the construction, we pick $a=196$. Then it is not hard to check that $19 \mid P(a+1)$ and $19 \mid P(a+5)$. $7 \mid P(a+2)$ and $7 \mid P(a+4)$. $3 \mid P(a+3)$ and $3 \mid P(a+6)$. holds. We are left to show that $b \geq 6$. It is not hard to show that the following statements are true: $\gcd(P(n), P(n+1))=1$ for all $n$. $\gcd(P(n), P(n+2))=1$ unless $n \equiv 2 \ (\textrm{mod} \ 7)$. $\gcd(P(n), P(n+3))=1$ unless $n \equiv 1 \ (\textrm{mod} \ 3)$. It follows from the first statement that $b \geq 4$. First, assume that $b=4$. Then, statement one implies that $\gcd(P(a+1), P(a+3)) \neq 1$ and $\gcd(P(a+2), P(a+4)) \neq 1$, hence $a+1 \equiv 2 \ (\textrm{mod} \ 7)$ and $a+2 \equiv 2 \ (\textrm{mod} \ 7)$ a contradiction. Now, suppose that $b=5$. Notice that by the first statement, we find that either $\gcd(P(a+1), P(a+3)) \neq 1$ or $\gcd(P(a+3), P(a+5)) \neq 1$. Either way, we get that $\gcd(P(a+2), P(a+4))=1$, which implies that $\gcd(P(a+1), P(a+4)) \neq 1$ and $\gcd(P(a+2), P(a+5)) \neq 1$. For this to be true, we must have $a+1 \equiv 1 \ (\textrm{mod} \ 3)$ and $a+2 \equiv 1 \ (\textrm{mod} \ 3)$, a contradiction. $\blacksquare$

We claim the minimal value of $b$ is $6$. The construction can be described as follows: Consider the set of numbers $S = \{P(a+1), P(a+2), P(a+3), P(a+4), P(a+5), P(a+6)\}$ where $a+3 \equiv a+6 \equiv 1 \pmod{3}, a \equiv 0 \pmod{7}, a+1 \equiv 7 \pmod{19}$ and $a \geq 0$. By the Chinese Remainder Theoreom, we know that such a value of $a$ exists. We claim that $S$ is fragrant. Note that $P(1) = 3, P(2) = 7, P(4) = 21, P(7) = 57, P(11) = 133$. The implication of this is that when $n \equiv 1 \pmod{3}, P(n) \equiv 0 \pmod{3}$, when $n \equiv 2 \pmod{7}, P(n) \equiv 0 \pmod{7}$, when $n \equiv 4 \pmod{7}, P(n) \equiv 0 \pmod{7}$, when $n \equiv 7 \pmod{19}, P(n) \equiv 0 \pmod{19}$, and when $n \equiv 11 \pmod{19}, P(n) \equiv 0 \pmod{19}$. Thus in our set, $P(a+3) \equiv P(a+6) \equiv 0 \pmod{6}, P(a+1) \equiv P(a+5) \equiv 0 \pmod{19}$, and $P(a+2) \equiv P(a+4) \equiv 0 \pmod{7}$. Now our goal is to show that no smaller value of $b$ works. We will prove this through a series of intermediate deductions. Claim: Note that $\gcd(P(n), P(n+1)) = 1$ for all integers $n \geq 1$. We can show this through the Euclidean algorithm. We have that $\gcd(P(n), P(n+1)) = \gcd(n^2 + n + 1, n^2 + 3n + 3) = \gcd(2n+2, n^2+n+1)$. Note that $n^2 + n + 1$ is odd, so we can further reduce this to $\gcd(n+1, n^2 + n + 1) = \gcd(n+1, n(n+1) + 1) = \gcd(1, n+1) = 1$. Clearly $b \neq 1$ by the definition of a fragrant set. The claim above immediately shows that $b \neq 2$. Moreover, $b \neq 3$. This can be proven simply through contradiction. Suppose the set $S = \{P(a+1), P(a+2), P(a+3)\}$ is fragrant where $a \geq 0$. Note that $\gcd(P(a+1), P(a+2)) = \gcd(P(a+2), P(a+3)) = 1$. This means that $P(a+2)$ does not share a common factor with any other term in $S$. Now, we show that $b \neq 4$. Consider for any $a \geq 0$, the set $S =\{P(a+1), P(a+2), P(a+3), P(a+4)\}$. In order for $S$ to be fragrant, we require that $\gcd(P(a+2), P(a+4)) \neq 1$ and $\gcd(P(a+1), P(a+3)) \neq 1$. We can think about which integers $n$ allow for $\gcd(P(n), P(n+2)) \neq 1$. This requires that there exists some prime $p$ such that $P(n) \equiv n^2 + n + 1 \equiv 0 \pmod{p}$ and $P(n+2) \equiv n^2 + 5n + 7 \equiv 0 \pmod{p}$. Now $p > 2$ since $P(n)$ is always odd. Subtracting the congruences, we see that $4n + 6 \equiv 0 \pmod{p} \implies 2n + 3 \equiv 0 \pmod{p} \implies n + \frac{3(p+1)}{2} \equiv 0 \pmod{p} \implies n \equiv \frac{(p-3)(p+1)}{2} \pmod{p}$. Substituting this into the congruence $n^2 + n + 1 \equiv n(n+1) + 1 \equiv 0 \pmod{p}$, we see that $(\frac{(p-3)(p+1)}{2})(\frac{(p-3)(p+1)}{2} + 1) + 1 \equiv 0 \equiv ((p-3)(p+1))((p-3)(p+1)+2)+4 \equiv 7 \equiv 0 \pmod{p} \implies p = 7$. This means that $n \equiv 2 \pmod{7}$. This means that $S$ cannot be fragrant as we require that both $a+1$ and $a+2$ be congruent to $2 \pmod{7}$. Lastly, we must show that $b \neq 5$. Consider for any $a \geq 0$, the set $S = \{P(a+1), P(a+2), P(a+3), P(a+4), P(a+5)\}$. Suppose that $\gcd(P(a+2), P(a+4)) \neq 1$. This means that $\gcd(a+1, a+3) = 1$ and $\gcd(a+3, a+5) = 1$ due to the analysis above. This means that $P(a+3)$ will be relatively prime to all other elements in $S$. So it must mean that $\gcd(P(a+2), P(a+5)) \neq 1$ and that $\gcd(P(a+1), P(a+4)) \neq 1$. Now let us analyze when $\gcd(P(n), P(n+3)) \neq 1$. We require that $\gcd(P(n), P(n+3)) = \gcd(n^2 + n + 1, n^2 + 7n + 13) \neq 1$. This means there is some prime $p$ such that $n^2 + n + 1 \equiv 0 \pmod{p}$ and that $n^2 + 7n + 13 \equiv 0 \pmod{p}$. Subtracting the congruences, we see that $6n + 12 \equiv 0 \pmod{p} \implies 3n + 6 \equiv 0\pmod{p}$. This means that either $n \equiv -2 \pmod{p}$ or that $p = 3$. If $n \equiv -2 \pmod{p}$, then $n^2 + n + 1 \equiv 0 \pmod{p} \implies 4 - 2 + 1 \equiv 3 \pmod{p} \implies p = 3$. So either way, we derive that $p = 3$, and that $n \equiv 1 \pmod{3}$. This means it is not possible for both $\gcd(P(a+1), P(a+4))$ and $\gcd(P(a+2), P(a+5))$ to not be $1$. Thus, we have achieved a construction for $b = 6$, and disproved $b = 1, 2, 3, 4, 5$. This collectively shows that our answer is $b = 6$.

xiexie wrote: Here is a method that gives some motivation to the bash. We claim that $\gcd(P(a),P(a+k))$ divides $k^3+3k$. Note that $P(a+k)-P(a)=2ak+k^2+k$. Therefore $$a\cdot[P(a+k)-P(a)]-2kP(a)=[(2k)a^2+(k^2+k)a]-[(2k)a^2+(2k)a+(2k)]=(k^2-k)a-2k.$$Thus this GCD divides both the expressions $C=2ak+k^2+k$ and $D=(k^2-k)a-2k$. We expand $C(k-1)$ and $2D$ and take the difference: $$C(k-1)-2D=[2k(k-1)a+k^3-k]-[2k(k-1)a-4k]=k^3+3k.$$Thus this GCD must divide $k^3+3k$. In fact, since $P(a)$ is always odd, the GCD must divide the greatest odd factor of $k^3+3k$. We can also show that $\gcd(P(a),P(a+1))=1$ using a similar, less-complicated method. How we performed the bash is, for the case $b=n$, we wrote $n$ blanks on the board, used this GCD property to label what each blank must be divisible by, and gradually showed that we could find two adjacent blanks that were divisible by the same number. This violates the fact that the GCD of $P(a)$ and $P(a+1)$ is 1. Once we found a suitable distribution of numbers for $b=6$, we all said "Chinese Remainder Theorem" and patted ourselves on the back. xiexie

Denote the assertion $A(x,y)$ to represent $\gcd(P(x),P(y))>1$. We can bash through some cases: \begin{align*} A(k,k+1) &\implies \text{No solution.} \\ A(k,k+2) &\implies k \equiv 2 \pmod 7 \\ A(k,k+3) &\implies k \equiv 1 \pmod 3 \\ A(k,k+4) &\implies k \equiv 7 \pmod{19}. \end{align*} We can verify $b=2,3,4,5$ all fail, and our construction for $b = \boxed{6}$ is \begin{align*} a+1 &\equiv 7 \pmod{19} \\ a+2 &\equiv 2 \pmod 7 \\ a+3 &\equiv 1 \pmod 3. \quad \blacksquare \end{align*}

The answer is $b=6$. Let $p$ be a prime. If the quadratic equation \[n^2 + n + 1 \equiv 0 \pmod{p}\]has solutions, by Vieta's formulas, the two roots must sum to $-1$ mod $p$. Now we find $p$ for which the roots differ by a small amount: If there are two consecutive roots $n$, they must be congruent to $0$ and $-1$ respectively. However, plugging either root in gives no solution. If there are two roots which differ by $2$, they must be $-\tfrac{3}{2}$ and $\tfrac{1}{2}$. Plugging either root in forces $p=7$. If there are two roots which differ by $3$, they must be $-2$ and $1$. Plugging either one in forces $p=3$. If there are two roots which differ by $4$, they must be $- \tfrac{5}{2}$ and $\tfrac{3}{2}$. Plugging either one in forces $p = 19$. Combinatorical reasons make it evident that $b$ can't be $2$, $3$, $4$ or $5$. So, it must be $6$ which is obtainable by setting $a = 196$. In that case, $P(197)$ and $P(201)$ share a prime factor of $19$; $P(198)$ and $P(200)$ share a prime factor of $7$; $P(199)$ and $P(202)$ share a prime factor of $3$. (I'm pretty sure there's nothing special about the quadratic $n^2 + n + 1$. This can be any quadratic and the same casework solution works.)

i dont know any cubic residue theory so i derived it myself Lemma. Let $p>3$ be a prime. Then $1$ has exactly $3$ cube roots in $\mathbb{F}_p$ if $3\mid p-1$, and one cube root otherwise. Proof. Let us work in $\mathbb{F}_p$. Note that $x^2+x+1=\frac{x^3-1}{x-1}$ so the roots of $x^2+x+1$ are the cube roots of $1$ other than $1$. Suppose $x^2+x+1$ splits in $\overline{\mathbb{F}_p}$ as $(x-\alpha)(x-\beta)$. Note that $\alpha,\beta\neq 0$. If $\alpha\in\mathbb{F}_p$, then $\beta=-1-\alpha\in\mathbb{F}_p$. It follows that $1$ has either $1$ or $3$ cube roots in $\mathbb{F}_p$. Consider the endomorphism $\varphi:\mathbb{F}_p^\times\rightarrow\mathbb{F}_p^\times$ given by \[ a\mapsto a^3 \]Let $G$ be the image of $\varphi$. If $\alpha,\beta\in\mathbb{F}_p$ (equivalently $\alpha,\beta\in\mathbb{F}_p^\times$), then $\ker\varphi=\{1,\alpha,\beta\}$ so $|G|=\frac{p-1}{3}$ and $3\mid p-1$. Now assume $3\mid p-1$. Let $g$ be a primitive root of $\mathbb{F}_p^\times$. Then $G$ is generated by $g^3$, which has order $\frac{p-1}{3}$ in $\mathbb{F}_p^\times$. Thus $|G|=\frac{p-1}{3}$ so $|\ker\varphi|=3$. It follows that $\alpha,\beta\in\mathbb{F}_p$. $\square$ We claim the answer is $\boxed{b=6}$. Note that if $n\equiv 1\pmod{3}$, $3\mid P(n)$. By Lemma, any prime dividing $P(n)$ is either $3$ or is congruent to $1$ modulo $3$. Note that the smallest prime congruent to $1$ modulo $3$ is $7$. Claim. Let $p\equiv 1\pmod{3}$ be a prime. Let $\alpha$ and $\beta$ be the cube roots of $1$ in $\mathbb{F}_p$ other than $1$. If $\alpha-\beta\in\{-4,-3,-2,-1,1,2,3,4\}$ (in $\mathbb{F}_p$) then $p\in\{7,19\}$. Proof. Let us work in $\mathbb{F}_p$. Let $d:=\alpha-\beta$. Since $\alpha$ and $\beta$ are the roots of $x^2+x+1$, it follows that $\alpha+\beta=-1$. Thus $\alpha=\frac{d-1}{2}$. WLOG we only need to consider $d\in\{1,2,3,4\}$. We have: \begin{align*} d=1&\implies\alpha=0 &&\implies\text{bad}\\ d=2&\implies\alpha=2^{-1}\implies 2^3=1 &&\implies p=7\\ d=3&\implies\alpha=1 &&\implies\text{bad}\\ d=4&\implies\alpha=\frac{3}{2}\implies 3^3=2^3 &&\implies p=19 \end{align*}so we are done. $\square$ Note that in $\mathbb{F}_7$ the cube roots of $1$ are $1,2,4$ and in $\mathbb{F}_{19}$ the cube roots of $1$ are $1,7,11$. It follows that \begin{align*} \gcd(P(n),P(n+1))&=1\\ \gcd(P(n),P(n+2))&>1\iff n\equiv 2\pmod{7}\\ \gcd(P(n),P(n+3))&>1\iff n\equiv 1\pmod{3}\\ \gcd(P(n),P(n+4))&>1\iff n\equiv 7\pmod{19} \end{align*}It is easy to check that $b=2,3,4,5$ do not work. If $b=6$ then we can let $a$ be a solution to \begin{align*} a+1&\equiv 1\pmod{3}\\ a+2&\equiv 7\pmod{19}\\ a+3&\equiv 2\pmod{7}, \end{align*}which exists by CRT. $\square$

We claim that the answer is $b = 6,$ which is achieved by setting $a = 196.$ Now we show that all $b \le 5$ don't work. Call two integers $x$ and $y$ buddies if $\gcd(x,y) \ne 1;$ the condition that a set is fragrant is equivalent to every member of the set having a buddy. Clearly $b = 1$ doesn't work since fragrant sets must have at least $2$ elements. Also, $$\gcd(P(n), P(n+1)) = \gcd(n^2 + n + 1, n^2 + 3n + 3) = \gcd(2n+2, n^2 + n + 1) = \gcd(n+1, n^2 + n + 1) = \gcd(n+1, 1) = 1$$since $P(n)$ is always odd, immediately eliminating $b = 2$ and $b = 3$ (just look at the middle element). Next, we tackle $b = 4.$ Assume for the sake of contradiction that $\{P(a+1), P(a+2), P(a+3), P(a+4)\}$ is fragrant. Look at $P(a+2)$: it can be buddies with neither $P(a+1)$ nor $P(a+3)$ from what we said above, so it must be buddies with $P(a+4).$ Letting $x = a + 2$, we get by repeatedly applying the Euclidean Algorithm and noting that $x^2 + x + 1$ and $2x+3$ are odd that \begin{align*} \gcd(P(x), P(x+2)) &= \gcd(x^2 + x + 1, x^2 + 5x + 7) \\ &= \gcd(4x+6, x^2 + x + 1) \\ &= \gcd(2x+3, x^2 + x + 1) \\ &= \gcd(2x+3, 2x^2 + 2x + 2) \\ &= \gcd(2x+3, 2x^2 + 2x + 2 - x(2x+3)) \\ &= \gcd(2x+3, 2 - x) \\ &= \gcd(7, 2 - x) \ne 1, \end{align*}so $x \equiv 2 \pmod{7}.$ Thus $a \equiv 0 \pmod{7}.$ Similarly, $P(a+3)$ must be buddies with $P(a+1),$ implying that $a \equiv 6 \pmod{7},$ contradiction. Thus $b \ne 4.$ The last order of action is to show that $b = 5$ doesn't work. Suppose it did work, and that the set $\{P(a+1), P(a+2), P(a+3), P(a+4), P(a+5)\}$ is fragrant. Then $P(a+3)$ must be buddies with at least one of $P(a+1)$ and $P(a+5),$ so either $a \equiv 6 \pmod{7}$ or $a \equiv 1 \pmod{7}.$ Now look at $P(a+2).$ It can't be buddies with $P(a+1)$ or $P(a+3),$ and if it were buddies with $P(a+4),$ then $a \equiv 0 \pmod{7},$ contradiction. Thus $P(a+2)$ must be buddies with $P(a+5).$ But letting $y = a+2,$ we have that \begin{align*} \gcd(P(y), P(y+3)) &= \gcd(y^2 + y + 1, y^2 + 7y + 13) \\ &= \gcd(y^2 + y + 1, 6y + 12) \\ &= \gcd(y^2 + y + 1, 3y + 6). \end{align*}If $y \equiv 1 \pmod{3},$ then $y^2 + y + 1 \equiv 0 \pmod{3}$ and so $P(y)$ and $P(y+3)$ are indeed buddies. Otherwise, \begin{align*} \gcd(P(y), P(y+3) &= \gcd(y^2 + y + 1, y+2) \\ &= \gcd(y^2 + y + 1 - (y^2 + y - 2), y + 2) \\ &= \gcd(3, y+2) \ne 1, \end{align*}once again implying that $y \equiv 1 \pmod{3}.$ Thus in any case, $y \equiv 1 \pmod{3},$ so $a \equiv 2 \pmod{3}.$ However, by similar logic, $P(a+1)$ and $P(a+4)$ are buddies, so $a \equiv 0 \pmod{3},$ contradiction. Therefore, the minimum value of $b$ is $6,$ and we are done.

The answer is $\boxed{b = 6}.$ First, we will show that $a = 5$ does not work. We have that $$\gcd(a^{2}+a+1, (a+1)^{2}+(a+1)+1) = \gcd(2a+2, a^{2}+a+1) $$$$= \gcd(a+1, a^{2}+a+1) = 1,$$and $$\gcd(a^{2}+a+1, (a+2)^{2}+(a+2)+1) = \gcd(a^{2}+a+1, 4a+6) $$$$= \gcd(2a^{2}+2a+2, 2a+3) $$$$= \gcd(2-a, 2a+3) = 7 \textrm{ if } a \equiv 2 \pmod 7, 0 \textrm{ otherwise}.$$Similarly, $\gcd(a^{2}+a+1, (a+3)^{2}+(a+3)+1) = 9$ if $a \equiv 1 \pmod 3,$ and $1$ otherwise, and $\gcd(a^{2}+a+1, (a+4)^{2}+(a+4)+1) = 19$ if $a \equiv 7 \pmod 19,$ and $1$ otherwise. Now, take the list $\{P(a+1), P(a+2), P(a+3), P(a+4), P(a+5)\}.$ Assume for the sake of contradiction that this is a fragrant set. If $a+1 \not \equiv 7 \pmod 19,$ then $\gcd(P(a+1), P(a+5)) = 1.$ Now, $P(a+1)$ must share a factor with either $P(a+3)$ or $P(a+4).$ If $P(a+1)$ shares a factor with $P(a+4),$ then $P(a+2)$ must share a factor with $P(a+4),$ since it cannot share a factor with $P(a+5).$ Then, $P(a+5)$ cannot share a factor with $P(a+3),$ nor $P(a+2),$ and not with $P(a+1)$ by assumption. Thus, we have a contradiction. If it shares a factor with $P(a+3),$ then $P(a+2)$ cannot share a factor with $P(a+4),$ since $a+1$ and $a+2$ cannot both be $2 \pmod 7.$ So, $P(a+4)$ must share a factor with $P(a+1).$ But, then $P(a+5)$ cannot share a factor with $P(a+1),P(a+2), P(a+3),$ a contradiction. If $P(a+1)$ shares a factor with $P(a+5),$ we can consider the number that $P(a+3)$ shares a factor with. It must be either $P(a+1)$ or $P(a+5).$ WLOG it shares a factor with $P(a+1).$ Notice that $P(a+2)$ and $P(a+5)$ must share a factor, since $P(a+2)$ and $P(a+4)$ cannot share a factor. Now, $P(a+4)$ cannot share a factor with $P(a+2),$ or $P(a+1).$ Thus, we again have a contradiction. Thus, $\{P(a+1), P(a+2), P(a+3), P(a+4), P(a+5)\}$ is not fragrant. For $b=6,$ taking $a=196$ works. Notice that $P(197)$ and $P(201)$ are both multiples of $19.$ Also, $P(198)$ and $P(200)$ are both multiples of $7,$ and $P(199)$ and $P(202)$ are both multiples of $3.$ Thus, the set obtained from $a,b = 196, 6$ is fragrant.

ash1374 wrote: What about P(n)=n? I have a sol for 18

We claim that the answer is $\boxed{b=6}$. We see that \begin{align*} \gcd(P(n),P(n+d))&=\gcd(n^2+n+1, n^2+(2d+1)n+(d^2+d+1))\\&=\gcd(n^2+n+1,2dn+d^2+d)\\&=\gcd(n^2+n+1,dn+\frac{d^2+d}2). \end{align*} When $d=1$, $\gcd(n^2+n+1, n+1)=\gcd(n+1, 1)=1$. When $d=2$, \begin{align*} \gcd(n^2+n+1, 2n+3)&=\gcd(2n^2+2n+2, 2n+3)\\&=\gcd(2n+3,n-2)\\&=\gcd(n-2,7). \end{align*} When $d=3$, $3|\gcd(n^2+n+1, 3n+6)$ if $n\equiv 1\pmod3$. Otherwise, \begin{align*} \gcd(n^2+n+1, 3n+6)&=\gcd(n^2+n+1, n+2)\\&=\gcd(n+2,n-1)\\&=\gcd(n-1,3)\\&=1. \end{align*} When $d=4$, \begin{align*} \gcd(n^2+n+1, 4n+10)&=\gcd(2n^2+2n+2, 2n+5)\\&=\gcd(2n+5,n-7)\\&=\gcd(n-7,19). \end{align*} This shows that $a=195$ works for $b=6$ because $$\gcd(P(196), P(199))=3, \gcd(P(197), P(201))=19, \gcd(P(198), P(200))=7.$$ It is easy to see that $b\le 5$ is not doable.