Новогодняя задача 2025

[nnosipov]

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

Существуют ли натуральные числа $a$ и $b$, для которых

$$\frac{(a+b+1)^2}{ab}=2025\;?$$

И тот же вопрос в случае равенства

$$\frac{(a+b+1)^2}{ab}=\frac{2025}{2}.$$

Всех с наступающим Новым годом!

[Shadow]

nnosipov в сообщении #1667968 писал(а):

Существуют ли натуральные числа $a$ и $b$, для которых

$$\frac{(a+b+1)^2}{ab}=2025\;?$$

С помощью Vieta jumping нетрудно доказать, что (если ничего не пропустил) $\dfrac{(a+b+1)^2}{ab}=k$ имеет решений при $k \in \{9,8,6,5\}$

В первом случае решения будут квадратами, во втором - квадрат и удвоенный квадрат, в третьем удвоенный и утроенный квадрат, в четвертом - квадрат и упятер, упять...квадрат, умноженный на $5$.

Вторую часть задачи оставлю для лучших времен.
С Новым Годом!

[nnosipov]

Shadow в сообщении #1668046 писал(а):

С помощью Vieta jumping нетрудно доказать, что (если ничего не пропустил) $\dfrac{(a+b+1)^2}{ab}=k$ имеет решений при $k \in \{9,8,6,5\}$

Да, конечно, все так и есть, но это было бы решением для знатоков. А по-простому (Новый год все-таки ) можно так. Из равенства $(a+b+1)^2=2025ab$ следует, что $a$ и $b$ взаимно просты. Учитывая, что $2025=45^2$, приходим к тому, что $a$ и $b$ должны быть квадратами: $a=x^2$, $b=y^2$. В итоге получаем $x^2+y^2+1=45xy$, что можно записать, например, так: $(x-y)^2+1=43xy$. Но $43$ --- простое число вида $4k+3$ и оно не может делить никакой квадрат, увеличенный на единицу.

Shadow в сообщении #1668046 писал(а):

Вторую часть задачи оставлю для лучших времен.

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

[Shadow]

nnosipov в сообщении #1668057 писал(а):

Учитывая, что $2025=45^2$

Да, надо привыкать. Значит, с вашей подсказкой, получим минимальное решение

$a = 44531997802090968110207001909255304366066384401$

$b = 44999539709699302763081486345495779014689601386888$

красиво
вот бы такие задачки любителям компютерного перебора.

[nnosipov]

Да, вот такая вот она, эта минимальная парочка $(a,b)$

[scwec]

Ещё одна пара (бесплатно)

$a = 45471990344653343351125731745121575439039476135065921$

$b = 44999539709699302763081486345495779014689601386888$

[nnosipov]

А эта побольше будет :) Как известно, у квадратного уравнения два корня.

[scwec]

Тут ведь дело сводится к решению уравнения Пелля $z^2-2017x^2=-8$. а имея одно решение, сложением получаются бесконечно много других.
Ну и корень квадратного уравнения не лишний, тем более что вычислять его труда не составляет. .

[nnosipov]

Да, все так. Напишу решение второго вопроса (на тот случай, если кому-то захочется увидеть решение от автора). Итак, имеем равенство $2(a+b+1)^2=2025ab$. Из-за симметрии будем считать $b$ четным (и тогда $a$ нечетно, как показывает рассмотрение по модулю $4$, но это неважно для дальнейшего). Полагая $b=2b_1$, получим $(a+2b_1+1)^2=2025ab_1$. Отсюда $a$ и $b_1$ взаимно просты, так что $a=x^2$, $b_1=y^2$ для некоторых натуральных $x$ и $y$. Теперь имеем $x^2+2y^2+1=45xy$, откуда

$$x=\frac{45y \pm \sqrt{2017y^2-4}}{2}.$$

Значит, $2017y^2-4=z^2$ для некоторого натурального $z$. Из сравнения $2017y^2-4 \equiv z^2 \pmod{8}$ следует, что $y$ и $z$ должны быть четными. Пусть $y=2y_1$, $z=2z_1$, тогда

$$z_1^2-2017y_1^2=-1.$$

Это так называемое негативное уравнение Пелля. Такие уравнения не всегда имеют решения, но это имеет. Почему? Потому, что $2017$ --- простое число вида $4k+1$, а есть такая теорема Лежандра: если $A$ --- простое число вида $4k+1$, то уравнение $u^2-Av^2=-1$ разрешимо (нетрудно выводится из разрешимости обычного уравнения Пелля $u^2-Av^2=1$, что мы примем за медицинский факт). Таким образом, принципиально вопрос решен: искомые $a$ и $b$ существуют. Но вот вопрос предъявления конкретной пары $(a,b)$ требует разложения $\sqrt{2017}$ в цепную дробь, и здесь уже без компьютера не обойтись, как можно судить по размерам минимальной пары $(a,b)$, см. выше. Ну, вот такой год попался

[Rak so dna]

Да. Минимальное решение выглядит круто. Интересно, а есть ли какие-нибудь теоремы\гипотезы об оценках минимальных решений уравнений Пелля (что-то типа Гипотезы Холла ) ?

[nnosipov]

Rak so dna
Вот в этой статье можно найти оценки: Solving the Pell Equation (см. раздел Efficiency). Для уравнения $x^2-dy^2=1$ верхняя граница для минимального решения экспоненциальна по $\sqrt{d}$. Она достигается, что можно прочувствовать на примере значений $d=5^{2k-1}$, где $k$ --- натуральное число.

[Rak so dna]

nnosipov т.е., если я правильно понял, существует константа $C$ такая, что для всех $d$ верны оценки

$$x_1<\dfrac{e^{C\sqrt{d}}}{2}+\dfrac{1}{4\sqrt{d}}$$

$$y_1<\dfrac{e^{C\sqrt{d}}}{2\sqrt{d}}$$

Они точные для бесконечного множества некоторых $d$, однако значение $C$ неизвестно.

[nnosipov]

Rak so dna в сообщении #1668308 писал(а):

существует константа $C$

Насколько я понял, существование такой константы не доказано, а доказанная оценка хуже: $R_d$ меньше, чем что-то типа $\sqrt{d}\log{d}$. И достигается ли эта доказанная оценка сверху, я не знаю.

В моем примере с $d=5^{2k-1}$ константу можно явно указать (минимальное решение явно выписывается).

[Rak so dna]

Ну да, очевидно, что такой $C$ не существует. Иначе из оценки

$\dfrac{e^{C\sqrt{d}}}{2}<x_1<\dfrac{e^{C\sqrt{d}}}{2}+\dfrac{1}{4\sqrt{d}}$

мы бы тупо нашли $x_1$ для всех больших $d$. То, что я написал, верно лишь для некоторых $d$ специального вида.

Ну а правильная оценка для $d=2017$ даёт $44<x_1<2\cdot 10^{214}$. Будет крайне удивительно, если сверху она будет точной хоть для какого-то большего $d$