Сложность текста: 2-3/5

Необходимые знания: должно быть достаточно основ теории многочленов, например формул Виета

На случай, если современная культура окажется утерянной во времени, дам немного контекста, чтобы вы понимали, почему эта задача стоит изучения.

Интернет переполнен «математическими задачками с эмодзи», которые выглядят примерно так:

Они более-менее продуманы, поэтому в них легко запутаться (приглядитесь к бананам), и у людей получаются разные ответы, что вызывает споры и обсуждения, делая посты виральными и так далее...

Естественно, настоящим математикам это надоело. В начале 2017 года на Reddit появился пост с заголовком «Меня утомила вся эта фейсбучная фруктовая математика. Хочет кто-нибудь придумать действительно сложную математическую задачу, чтобы побороться с этим явлением?». Один пользователь создал такую картинку:

Она не особо сложна. Её можно легко решить для целых чисел, если быть терпеливым или перебрать все варианты. Но здесь начинается самое интересное.

Пользователь по имени Сридхар Рамеш увидел эту картинку и решил внести небольшое изменение, прежде чем распространять её.

Благодаря этому задача стала ужасно сложной. Самое маленькое решение имеет длину более восьмидесяти разрядов. Доктор Алон Амит назвал её «умной и злой шуткой». Считается, что для её решения нужен высокий уровень знаний в области эллиптических кривых.

Но когда это нас останавливало? В посте мы решим эту задачу. Точнее, я опишу, как наконец-то решил её.

Разогреемся

Для начала попробуем решить задачу попроще:

Задача: найти все пифагоровы тройки.

Решение. Нам нужно решить диофантово уравнение 

для неотрицательных целых чисел. Но это неприятно. Мы были бы гораздо счастливее, если бы нужно было вместо этого решить

где и — неотрицательные рациональные числа. По сути, это та же задача, потому что решение

эквивалентно решению

То есть мы, по сути, принимаеми.

Мы так довольны этим, потому что теперь задача формулируется как «найти все рациональные точки в единичной окружности», где рациональная точка — это просто точка с рациональными координатами. Действительно ли это легче сделать?

Вот трюк, который позволит решить задачу.

1. Начнём с нахождения какой-нибудь подходящей точки. Я возьму.

2. Проведём прямую с рациональным наклоном, проходящую через. Что-то типа, гдерационально.

3. Она будет всегда (практически) пересекать окружность во второй точке.

4. Тогда всегда будет ещё одной рациональной точкой!

Почему это так? Чтобы найти координаты этой второй точки, мы решаем систему уравненийи. Однако мы уже знаем одно решение:. Поэтому мы избавляемся от, чтобы получить квадратичное уравнение

Мы можем рассуждать следующим образом:

• Коэффициенты уравнения рациональны.

• Следовательно, по формулам Виета, сумма корней рациональна.

• Мы знаем, что один корень рационален, потому что провели прямую через рациональную точку. Следовательно, другой корень должен быть рациональным.

• Еслирационален, торационально; следовательно,рационально.

• Следовательно, вторая точка пересечения этой прямой с окружностью — это рациональная точка.

Можно сделать вывод, что, проведя любую прямую с рациональным наклоном через, мы получим ещё одну рациональную точку на окружности. Но и это ещё не всё. Обратим внимание, что если— ещё одна рациональная точка, то прямая, соединяющаяи, должна иметь рациональный наклон. То есть, если мы проведём каждую прямую рациональной точки через, то получим ВСЕ возможные рациональные точки на окружности.

Давайте найдём эту вторую точку для всех возможных наклонов. Развернув уравнение, получим:

Мы уже знаем, чтобыл корнем, поэтому координата, которую мы ищем — это ещё один корень, который задаётся как. Соответствующее значение дляимеет вид. Сократив делители и подчистив знаки, мы увидим, что ВСЕ пифагоровы тройки можно охарактеризовать следующим образом:

для положительных чиселвплоть до какого-то целочисленного кратного. Это очень удобное свойство из олимпиадной теории чисел, о котором вы могли слышать.

Важный вывод здесь заключается в том, что проводя прямые, мы будем получать новые точки. Выше мы провели лишь одну прямую через точку, чтобы получить ещё одну точку. Хоть это не подходит для решения исходной задачи, принцип очень похож. Давайте приступим!

Приступаем к решению

Итак, мы начинаем со следующего уравнения:

Подчистив знаменатели, мы в конечном итоге придём к следующему:

Вместо того, чтобы пытаться решить это в положительных числах, мы выразим уравнение относительнои, попробовав найти рациональные точки, положительные и отрицательные. Будем надеяться, что это упростит решение.

Разделив уравнение на, мы получим

График этого уравнения будет выглядеть так:

Можно заметить, что он «повёрнут» на. Это логично, потому что перемена местами ине должна ничего менять в показанном выше уравнении.

Для моего собственного удобства (этот шаг необязателен, но я его сделал) я решил повернуть график, чтобы он был симметричным относительно оси. Я сделал это, подставиви . Теперь это уравнение с новыми рациональными переменнымии, а уравнение принимает вид:

Так гораздо удобнее. Теперь график выглядит так:

Красиво и симметрично! Такая кривая называется эллиптической.

Достаточно посмотреть на график, чтобы увидеть очевидные рациональные точки:,и, которые я обозначу,и. (Тому есть причины, о которых мы поговорим во второй части статьи.)

К сожалению, нахождение этих точек не означает, что мы решили задачу. Они соответствуют неправильным решениям исходной задачи. Но можем ли мы использовать эти «лёгкие точки», чтобы найти другие?

Эпичное возвращение трюка с прямыми

Получить ещё больше точек нам позволит следующий процесс.

1. Начинаем с двух рациональных точеки, лежащих на эллиптической кривой.

2. Проводим прямую. Отмечаем, что она имеет рациональный наклон, потому чтои— рациональные точки.

3.   всегда будет пересекать эллиптическую кривую в третий раз (включая кратность) в точке.

4. Более того,всегда будет ещё одной рациональной точкой!

Здесь нужно объяснить некоторые аспекты: почему прямая будет пересекаться в третий раз и почему третье пересечение должно быть рациональной точкой? Мы рассуждаем следующим образом, аналогичным предыдущим рассуждениям из раздела «Разогреваемся»:

• Третья точкаудовлетворяет системе уравнений

  где— уравнение прямой, проходящей через точкии
  .

• Если мы найдёмиз второго уравнения и подставим его в первое уравнение, чтобы сократить переменную, то у нас останется кубическое уравнение для.

• Это кубическое уравнение имеет рациональные коэффициенты, потому что коэффициентыидолжны быть рациональными, поскольку прямая имеет рациональный наклон и проходит через рациональные точки.

• Следовательно, по формулам Виета, сумма корней кубического уравнения — это рациональное число.

• Два корня определяются координатамиточеки, а обе они рациональны.

• Следовательно, третий корень рационален. Это значит, что координататочкирациональна.

• Воспользовавшись, мы можем сделать вывод, что координататоже рациональна. Следовательно,— рациональное число.

Отлично! Важное дополнение: пересечения подсчитываются с учётом кратности. Допустим, можно взятьитак, чтобы они были одной точкой. Тогда «прямая» на самом деле будет касательной к кривой в точке, но всё равно будет работать. Обязательно разберитесь, почему это так!

Теперь мы знаем, что если соединить две рациональные точки эллиптической кривой, то можно получить ещё одну рациональную точку на кривой. Давайте попробуем это сделать.

Соединивипрямой, мы найдём, что существует третье пересечение в.

И в самом деле, если мы подставим эти значения, то всё сойдётся! Что ещё можно получить?

«Соединивипрямой» или взяв касательную к, мы можем найти ещё одно третье пересечение с кривой.

На этот раз она находится в. Это довольно просто: мы могли бы выяснить это, взяв предыдущую полученную точку и отразив её относительно оси. Можем ли мы легко получить что-то ещё? На самом деле, нет. Причина в том, что этиточек (и ещё одна скрытая «точка», о которой я не буду говорить) — это точки кручения. Сколько бы раз мы ни повторяли этот трюк с прямой, новых точек мы не получим.

Это плохо. Как же нам получить точки, которые «сбежали» от этихточек?

Находим больше точек (бесконечного порядка)

Я довольно глупый, поэтому написал код Mathematica, чтобы попробовать найти менее тривиальные точки кривой.

И мне удалось найти красивые точки! Я долго экспериментировал с точками, но оказалось, что нам подходит первая точка. Я обозначу эту точку

Прежде чем мы перейдём к поиску других точек, нужно осветить два момента.

Во-первых, какую рациональную точку я пытаюсь найти? Если мы проверим, то выясним, что она не подходит, потому что некоторые из получившихся переменныхмогут оказаться отрицательными. Поэтому мы пытаемся найти рациональные точки, такие, чтобы они соответствовали полностью положительной тройке. Когда такое происходит? Давайте порассуждаем об этом, немного вернувшись назад.

• Мы можем предположить, что какая-то переменная (без потери общности) положительна, потому что если все переменныеотрицательны, мы получим положительное решение, поменяв все знаки.

• Тогда, если. То есть.

• Это значит, что нам нужнои. Иными словами,.

Это соответствует следующей зелёной области:

Повторимся: наша цель — найти рациональное число на кривой, лежащей в этой области. Следовательно, задача превращается в забавный «математический футбол»: нам нужно использовать трюк с прямыми для генерации всё большего количества точек, пока мы не достигнем «гола», то есть зелёной области.

Вручную это делать крайне утомительно. К счастью, у меня есть Mathematica! Это подводит нас ко второму вопросу, который я хотел рассмотреть: как нам упростить наш трюк с прямыми?

Выполнив развёртывание при помощи Mathematica, я выяснил, что кубическое уравнение. полученное из нахождения третьего пересечения прямой, проходящей через точкии, имеет сумму корней, задаваемую следующим образом:

То есть, по формулам Виета, мы можем написать формулу для координатытретьего пересечения:

Аналогично, мне удалось записать формулу для третьего пересечения, имея касательную в точке:

Как некрасиво! Именно поэтому числа будут огромными.

Кроме того, эти формулы дают нам только координаты. Координату(положительную) легко можно найти при помощи одной последней формулы, которая достаточно просто выводится (можно буквально просто выразить):

А теперь давайте закончим наш бой.

Финал

Изя проведу касательную и найду третье пересечение в новой точке. (Здесь тоже не стоит беспокоиться о названиях!)

Наши формулы дадут координаты для:

Изя проведу ещё одну касательную и найду третье пересечение в новой точке.

Mathematica снова подскажет нам координатыпри помощи формул.

Мы пока не смогли попасть в зелёную область, поэтому нужно продолжать двигаться дальше. Как это ни неприятно, я проведу ещё одну касательную в, чтобы получить точку:

Она имеет следующие координаты:

С касательными мы закончили! Для удобства я нанёс на график точку, которая просто соответствуетс обратной координатой, и соединилспрямой, чтобы получить точку:

Координаты:

В этом и заключался мой великий план! Мне нужна была настолько высокая точка, чтобы наконец попасть в зелёную область с ещё одной прямой. Что это за прямая? Рад, что вы спросили! Всё это время оставлял на последний момент одну последнюю «красивую» рациональную точку:! Проведя прямую междуи, мы наконец-то окажется в точке в зелёной области:

Координаты:

Свет в конце туннеля уже близок! Сделав эту последнюю точку, мы вычислими, чтобы получитьи:

Вспомнив, что они равны, соответственно,и, мы сделаемнаименьшим общим кратным знаменателей, абудут итоговыми числителями, когда мы найдём общий знаменатель. Так мы получим это огромное решение... в положительных целых числах!

Чтобы по-настоящему оценить нашу работу, мы можем убедиться, что они действительно подходят.