Задача из журнала «Квант» (1999 год, 3 выпуск)

Условие

Арифметическая прогрессия из натуральных чисел содержит не менее трех членов, их произведение – делитель некоторого числа $n^2 + 1$.

1. Докажите, что существует такая прогрессия с разностью $12$.
2. Докажите, что такой прогрессии с разностью $10$ или $11$ не существует.
3. * Какое наибольшее число членов может содержать такая прогрессия с разностью $12$?

Решение

1. Рассмотрим числа $1$, $13$, $25$; для них $5^2 + 1 = 13\cdot2$,
   $7^2 + 1 = 25 \cdot 2$. Число $57^2 + 1$ делится на $13\cdot25$: к этому легко придти непосредственно, а общий метод см. ниже.
2. Из трех чисел $а$, $а + 10$, $а + 20$ одно делится на $3$, а $n^2 + 1$ на $3$ не делится.
   Случай разности $11$ рассматривается аналогично.
3. Ни один из членов прогрессии не делится на $7$, ибо на $7$ не делится $n^2 + 1$. Значит, из семи членов прогрессии (если бы такая была) можно было бы выбрать два, разность которых делится на $7$. Получили противоречие:
   $k\cdot 12$ кратно $7$ (пишут: $k\cdot 12 \vdots 7$), где $0 < k < 7$.

Докажем, что прогрессия из шести членов есть:

$\left(5, 17, 29, 41, 53, 65\right)$.

Нам нужно доказать существование такого числа $n$, что $n^2 + 1$ делится на

$$\begin{equation}\label{eq:exp1}5\cdot17\cdot 29\cdot 41\cdot 53\cdot 65 = \left( 25\right) \cdot 17\cdot 29\cdot 41\cdot 53\cdot 13.\end{equation}$$
Каждое из шести чисел в правой части $\eqref{eq:exp1}$ обладает
нужным свойством:

$\left(7 + 25x\right)^2 + 1 \vdots 25$, $\left(4 + 17y\right)^2+ 1 \vdots 17$,

$\left(12 + 29z\right)^2 + 1 \vdots 29$, $\left(9 + 41u\right)^2+ 1 \vdots 41$,

$\left(23 + 53v\right)^2 + 1 \vdots 53 \left( так \;как \;23^2 + 1 = 530\right),$

$\left(5 + 13w\right)^2+ 1 \vdots 13$.

Теперь нам понадобится предложение, известное как «китайская теорема об остатках».

Дополнение. Существуют ли более длинные арифметические прогрессии, удовлетворяющие всем условиям нашей задачи? На этот вопрос нетрудно ответить с помощью результатов статьи «Суммы квадратов и целые гауссовы числа» (см. «Квант» №3 за 1999 год).Именно, легко показать, что разность любой прогрессии задачи обязана делиться на $12$. С другой стороны, выше мы показали, что разность любой такой прогрессии, содержащей не менее семи членов, должна делиться на $7$.
Прогрессия задачи с разностью $12\cdot7 = 84$ существует: с помощью статьи «Суммы квадратов…» и китайской теоремы об остатках легко показать, что делителем некоторого числа $n^2 + 1$ является произведение всех членов
прогрессии $\left(29, 113, 197, 281, 365, 449, 533, 617, 701,785\right)$.
Эта прогрессия содержит $10$ членов; $11$ же членов прогрессия задачи с разностью $84$ содержать не может: $84$ не делится на простое число $р = 4k + 3 = 11$.

В.Сендеров