Можно обойтись без эллиптических кривых

Конкурсная задача ММ187 (6 баллов)

Доказать, что существует бесконечно много пар натуральных чисел , таких что является натуральным числом. Доказать, что существует бесконечно много пар, для которых . Существуют ли пары, для которых ?

Решение

Нарушу традиции и приведу решения Виктора Филимоненкова и Дмитрия Пашуткина (поразившее меня своей краткостью).

Обсуждение

Любопытна история ММ187. Лет двадцать назад задачу, послужившую основой ММ187, мне задал один абитуриент, когда принимал у него вступительный экзамен по математике. Случай в моей практике уникальный. Как выяснилось, исходная задача (IMO 1988) «широко известна в узких кругах». Например, метод Vieta jumping объясняется в англоязычной Википедии именно на примере этой задачи, а в русскоязычной Википедии ссылка на эту статью есть в статье «Олимпиадные математические задачи». Более того, статью «Vieta jumping» и ссылку на нее разместил Макс Алексеев - свой человек в Математическом марафоне. Так что, насчет узких кругов я написал не для красного словца.

Натуральными числами вида являются квадраты НОД(a,b) и только они. Я сознательно составил задачу так, чтобы справиться со всеми тремя пунктами можно было, не опираясь на это утверждение: для первого достаточно пар ; для второго просто строится рекуррентная последовательность для значения 1369; для третьего достаточно заметить, что 2013 делится на 3, но не делится на 9 (из решения Дмитрия Пашуткина видно, что можно прийти к верному выводу и иначе).

На этот раз марафонцы не особо стремились к обобщениям. Единственным участником, предложившим серьезное обобщение ММ187, оказался Олег Полубасов. Я не привожу этого обобщения по двум причинам: 1) я еще сам не конца разобрался во всех деталях (а разбор ММ187 и без того запаздывает); 2) те детали, в которых я успел разобраться, все равно, попридержу, поскольку они могут послужить основой для новых задач Замечу только, что Олег «танцевал» от тесной связи ММ187 с ММ135 и ММ164.

Награды

За правильное решение и обобщение задачи ММ187 Олег Полубасов получает 11 призовых баллов. За правильное решение задачи (или ее отдельных пунктов) Анатолий Казмерчук, Сергей Половинкин, Виктор Филимоненков, Дмитрий Пашуткин получают по 6 баллов, Евгений Гужавин - 4 балла, Николай Дерюгин и Владимир Дорофеев - по 2 призовых балла.

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