===== ММ135 =====
**Конкурсная задача ММ135** (4 балла)
Конечно ли множество пар натуральных чисел (a,b), таких что остатки от деления a2 на b и b2 на a равны по 2011?
**Решение**
Положим: a1=3234, a2=8467, ai+1=3ai-ai-1.
Легко проверяется и доказывается по индукции, что для любых трех соседних членов этой последовательности выполняется соотношение ai2=ai-1ai+1+2011, из которого следует, что любую пару соседних членов можно взять в качестве требуемых a и b.
Ответ: бесконечно.
**Обсуждение**
Существует много (возможно, бесконечно много) последовательностей, соседние члены которых будут подходящими парами. Например:
a1=2054, a2=18255, ai+1=9ai-ai-1;\\
a1=2090, a2=47979, ai+1=23ai-ai-1;\\
a1=2181, a2=10450, ai+1=5ai-ai-1;\\
a1=2545, a2=12194, ai+1=5ai-ai-1;\\
a1=3115, a2=40254, ai+1=13ai-ai-1;\\
a1=4298, a2=29459, ai+1=7ai-ai-1;\\
a1=4925, a2=12894, ai+1=3ai-ai-1.
Кроме того, существет много подходящих пар, в которых a и b не взаимно просты (разумеется, их НОД равняется 2011). Например, (4022, 6033) или (19*2011, 17285*2011). Но мне не удалось построить из таких пар какую-либо бесконечную серию.
Владислав Франк в качестве бесконечного множества подходящих пар использовал множество решений диофантова уравнения a2+b2-2011=37ab. А решение этого уравнеyия свел к решению обобщенного уравнения Пелля x2-1365y2=8044.
Разумеется, 2011 не является исключительным числом в смысле нашей задачи. Пусть m > 3. Положив a1=m2-3m+1, a2=m^3-5m2+6m-1, ai+1=(m-2)ai-ai-1, получим бесконечно много пар (соседних членов последовательности) таких, что остатки от деления ai2 на ai+1 и ai+12 на ai равны m.
Сергей Половинкин заметил, что члены последней последовательности - это в точности значения чебышевских полиномов второго рода с четными номерами при x=√(m)/2.
При m < 4 указанный метод уже не приводит к возрастающей последовательности натуральных чисел и не дает подходящих пар.
Однако, бесконечность подходящих пар для m=1 очевидна. Достаточно рассматривать пары соседних чисел. Более обще, если m=s2, то при 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).
Таким образом, ответ на второй вопрос остается открытым.
**Уже после опубликования этого разбора Дмитрий Пашуткин нашел бесконечные серии для случаев m = 3 и m = 2.**\\
Для m = 3 годятся пары (ai, bi), где a1 = 69, b1 = 39,\\
ai+1 = 16ai - 9bi,\\
bi+1 = 9ai - 5bi.
m = 3 и m = 2.\\
Для m = 2 годятся пары (ai, bi), где a1 = 1262, b1 = 92,\\
ai+1 = 10631719ai - 791904bi,\\
bi+1 = 791904ai - 58985bi.
**Награды**
К моему удивлению, с задачей ММ135 справились всего трое участников Марафона.
За правилное решение и обобщение задачи ММ135 Сергей Половинкин получает 7 призовых баллов. Владислав Франк и Алексей Волошин получают по 4 призовых балла.
**Дополнение**: Дмитрий Пашуткин получает 4 призовых балла
**Эстетическая оценка задачи ММ135 - 4.8 балла**
//Обзор задачи ММ135 подготовил Владимир Лецко//
----