57-я Международная Математическая OлимпиадаГонконг, 2016 год

Назовём множество, состоящее из положительных целых чисел, хрупким, если оно состоит не менее, чем из двух элементов, и каждый его элемент имеет общий простой делитель хотя бы с одним из остальных элементов этого множества. Пусть $P(n) = n^2+ n + 1$. Найдите наименьшее положительное целое $b$, для которого найдётся неотрицательное целое $a$ такое, что множество $\{P(a + 1), P(a + 2), \ldots, P(a + b)\}$ является хрупким.

Комментарий/решение

Решение: Заметим, что $$\gcd(P(n-1),P(n))=\gcd(n^2-n+1,n^2+n+1)=\gcd(n^2-n+1,2n)=\gcd(n,n^2-n+1,n)=1(1)$$ $$p|P(a+2),P(a)\Leftrightarrow p|a^2+a+1,2a+3\Rightarrow p|(2a+1)^2+3\equiv 2^2+3=7\Rightarrow7|a-2(2)$$ Из $(1)$ следует, что искомое $b\neq2,3$, из $(2)$ имеем $b\neq4$. Если $b=5$, то некоторые 3 числа из $\{ P(a+1),P(a+2),...,P(a+5)\}$ имеют общий простой делитель, иначе 5 чисел можно разбить на пары не взаимнопростых, т.е. 5 - чётное. Из $(1)$ эти 3 числа $P(a+1),P(a+3),P(a+5)$, откуда из $(2)$ $7|a-1,a+1$ - противоречие, поэтому $b\ge6$.

$$p|P(a),P(a+3)\Leftrightarrow p|6a+12,a^2+a+1\Leftrightarrow \\3|a-2\\p|P(a),P(a+4)\Leftrightarrow p|8a+20,a^2+a+1\Leftrightarrow\\p|2a+5,(2a)^2+4a+4\equiv19\Leftrightarrow 19|a-7$$ Теперь докажем существование такого $a$, что $$\gcd(P(a+1),P(a+5))=19,\gcd(P(a+2),P(a+4))=7,\gcd(P(a+3),P(a+6))=3$$ Из доказанного выше это равносильно $19|a-6,7|a,3|a-2$, очевидно такой существует по китайской теореме об остатках.

Ответ: 6