Решение задачи MM135 IV открытой интернет-олимпиады по математике: XIV тура Математического марафона

главная страница сайта Приглашение в мир математики
======= 135 ========

ММ135 (4 балла)

Конечно ли множество пар натуральных чисел $(a,b)$, таких что остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны по 2011?

===============

Решение

Положим: $a_1=3234, \ a_2=8467, \ a_{i+1}=3a_i-a_{i-1}$.
Легко проверяется и доказывается по индукции, что для любых трех соседних членов этой последовательности выполняется соотношение $a_i^2=a_{i-1}a_{i+1}+2011$, из которого следует, что любую пару соседних членов можно взять в качестве требуемых a и b.

Ответ: бесконечно. Обсуждение

Существует много (возможно, бесконечно много) последовательностей, соседние члены которых будут подхoдящими парами. Например:

$a_1=2054, \ a_2=18255, \ a_{i+1}=9a_i-a_{i-1}$;
$a_1=2090, \ a_2=47979, \ a_{i+1}=23a_i-a_{i-1}$;
$a_1=2181, \ a_2=10450, \ a_{i+1}=5a_i-a_{i-1}$;
$a_1=2545, \ a_2=12194, \ a_{i+1}=5a_i-a_{i-1}$;
$a_1=3115, \ a_2=40254, \ a_{i+1}=13a_i-a_{i-1}$;
$a_1=4298, \ a_2=29459, \ a_{i+1}=7a_i-a_{i-1}$;
$a_1=4925, \ a_2=12894, \ a_{i+1}=3a_i-a_{i-1}$.

Кроме того, существует много подходящих пар, в которых a и b не взаимно просты (разумеется, их НОД равняется 2011). Например, $(4022, 6033)$ или $(19\cdot 2011, 17285\cdot 2011)$. Но мне не удалось построить из таких пар какую-либо бесконечную серию.

Владислав Франк в качестве бесконечного множества подходящих пар использовал множество решений диофантова уравнения $a^2+b^2-2011=37ab$. А решение этого уравнения свел к решению обобщенного уравнения Пелля $x^2-1365y^2=8044$.

Разумеется, 2011 не является исключительным числом в смысле нашей задачи. Пусть $m>3$. Положив $a_1=m^2-3m+1, \ a_2=m^3-5m^2+6m-1, \ a_{i+1}=(m-2)a_i-a_{i-1}$, получим бесконечно много пар (соседних членов последовательности) таких, что остатки от деления $a_i^2$ на $a_{i+1}$ и $a_{i+1}^2$ на $a_i$ равны $m$.
Сергей Половинкин заметил, что члены последней последовательности - это в точности значения чебышевских полиномов второго рода с четными номерами при $x=\frac{\sqrt{m}}2$.

При $m<4$ указанный метод уже не приводит к возрастающей последовательности натуральных чисел и не дает подходящих пар.
Однако, бесконечность подходящих пар для $m=1$ очевидна. Достаточно рассматривать пары соседних чисел. Более обще, если $m=s^2$, то при $a>m$ пара $(a,a+s)$ будет подходящей.

Остаются два последних вопроса: Существуют ли подходящие пары для $m=2$ и $m=3$. И если существуют, то конечно ли их число?
Ответ на первый вопрос положителен. Для $m=3$ подходящими парами являются, например, (6, 33), (39, 69), (426, 753), (498, 19077), (789, 27066), (4647, 8214).
Для $m=2$ мне удалось подобрать всего одну пару (94, 1262).
Таким образом, ответ на второй вопрос остается открытым.

Награды

К моему удивлению, с задачей ММ135 справились всего трое участников Марафона.
За правилное решение и обобщение задачи ММ135 Сергей Половинкин получает 7 призовых баллов. Владислав Франк и Алексей Волошин получают по 4 призовых балла.

Эстетическая оценка задачи ММ135 - 4.8 балла

===============

Обзор задачи ММ135 подготовил Владимир Лецко

Задайте вопрос на блоге о математике