М1689. Задача об арифметической прогрессии

Задача из журнала «Квант» (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$.

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

Теорема. $a_1, \dotsc , a_m —$ натуральные числа, каждые
два из которых взаимно просты, $r_1, \dotsc , r_m —$произвольные целые числа. Тогда существуют целые числа $x_1, \dotsc , x_m$ такие, что

$a_1x_1+r_1=\dotsc=a_mx_m+r_m$.
При $m = 2$ теорема доказывается с помощью алгоритма Евклида, после чего ее утверждение распространяется на общий случай $m > 2$ по индукции.
Для окончания решения пункта в) достаточно применить теорему к системе уравнений $7 + 25x = 4 + 14y = \dotsc + 23+53v=5+13w$.

Дополнение. Существуют ли более длинные арифметические прогрессии, удовлетворяющие всем условиям нашей задачи? На этот вопрос нетрудно ответить с помощью результатов статьи «Суммы квадратов и целые гауссовы числа» (см. «Квант» №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$.

В.Сендеров

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *