Задача из кванта 1988 год, №1135

[sa233091]

Недавно, листая квант, я столкнулся с такой интересной задачей:
$\[a\]$ и $\[b\]$ такие натуральные числа, что $\[({a^2} + {b^2}) \vdots (1 + ab)\]$. Докажите, что частное - квадрат целого числа.
Сам долго думал и не к чему хорошему не пришел. Хотел доказать, что если $\[{a^2} + {b^2} = {p^x}m\]$ и $\[1 + ab = {p^y}n\]$ ( $\[p\]$ - простое, $\[\{ m;n\} \]$ не делятся на $\[p\]$), то $\[(x - y)\]$ - четно. То есть $\[\frac{{{a^2} + {b^2}}}{{1 + ab}}\]$ делится только на четную степень любого простого числа $\[p\]$. Но у меня возникли большие трудности. Прошу дать идею решения.

[Shadow]

Кажется, задача (или подобная) была на форуме. Решается с помощью метода Vieta jumping
Скачок Виета - здесь на русском.

Там есть и решение этой задачи.

[maxal]

См. также: topic95003.html

[sa233091]

Большое спасибо за материал

[maxal]

Добавил перевод в русскую Википедию: Прыжки Виета

[sa233091]

А есть ли ещё способы решения?

-- 22.09.2016, 00:36 --

Можно ли решить с помощью элиптических кривых?

[cmpamer]

sa233091 в сообщении #1153433 писал(а):

А есть ли ещё способы решения?

Разумеется

sa233091 в сообщении #1153433 писал(а):

Можно ли решить с помощью элиптических кривых?

Можно, наверное... Но лучше с помощью "эллиптических прямых", ибо прямая всегда проще кривой (двумя точками, говорят, определяется).
Такими исходными "точками" в предложенной задаче являются следующие легко доказываемые наблюдения:
1. Сумма квадратов двух любых натуральных чисел сравнима с квадратом разности этих чисел по модулю произведения этих же чисел ($a^2 + b^2= a^2 -2ab+ b^2 +2ab = (a-b)^2+2ab ..... $)
2. Численное значение исходного выражения всегда меньше произведения натуральных $ab$, коль скоро последнее больше единицы (тоже очевидная вещица).
В принципе - всё. Надо ещё только потеоретизировать по поводу соотношения $a/b (a>b)$. Вся "теория" сводится к решению квадратного уравнения (исходя из условия задачи о делимости суммы квадратов двух натуральных чисел на следующие за их произведением натуральное число) и сравнением этого решения с условием $(a-b)^2>ab$.
А дальше надо "промодулировать" исходное выражение по модулю "$ab$", обращая внимание при этом, что знаменатель будет "равен" единице (т.е. всё выражение будет равно (по остатку от деления на $ab$) "чистому" квадрату, ибо "b" не может быть меньше трети "a"). А поскольку частное меньше $ab$, то оно само и будет остатком от деления на это произведение, т.е. - квадратом натурального числа.

[sa233091]

cmpamer в сообщении #1153674 писал(а):

А дальше надо "промодулировать" исходное выражение по модулю "$ab$", обращая внимание при этом, что знаменатель будет "равен" единице (т.е. всё выражение будет равно (по остатку от деления на $ab$) "чистому" квадрату, ибо "b" не может быть меньше трети "a"). А поскольку частное меньше $ab$, то оно само и будет остатком от деления на это произведение, т.е. - квадратом натурального числа.

Так нельзя промодулировать, если $\[x \equiv {n^2}(\bmod ab),y \equiv 1(\bmod ab)\]$, то из этого не следует , что $\[\frac{x}{y} \equiv {n^2}(\bmod ab)\]$

[arseniiv]

(Формулы)

x\equiv n^2\pmod{ab} $x\equiv n^2\pmod{ab}$. \bmod — это операция взятия остатка.

[sa233091]

arseniiv в сообщении #1153708 писал(а):

(Формулы)

x\equiv n^2\pmod{ab} $x\equiv n^2\pmod{ab}$. \bmod — это операция взятия остатка.

А какая разница?

[arseniiv]

Значительная в пробелах.

$x \equiv {n^2}(\bmod ab),y \equiv 1(\bmod ab)$
$x\equiv n^2\pmod{ab},\;y\equiv 1\pmod{ab}$

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

$x\equiv n^2,\;y\equiv 1\pmod{ab}$

Или нельзя, но первое всё равно в силе.

[cmpamer]

sa233091 в сообщении #1153705 писал(а):

...если $\[x \equiv {n^2}(\bmod ab),y \equiv 1(\bmod ab)\]$, то из этого не следует , что $\[\frac{x}{y} \equiv {n^2}(\bmod ab)\]$

В общем случае - не следует. Но исходя из условий задачи - следует, т.к. и $n^2 = (a-b)^2$ меньше произведения $a\times b$, и $\[\frac{{{a^2} + {b^2}}}{{1 + ab}}\]$ - тоже меньше.

[sa233091]

Большое спасибо за решение задачи!
Оно мне показалось даже более красивым, чем предыдущее

[Shadow]

cmpamer в сообщении #1153731 писал(а):

т.к. и $n^2 = (a-b)^2$ меньше произведения $a\times b$

$a=8,b=2$ - одно из многих решений

[DeBill]

Т.е., идея "по модулю $ab$" хороша, но не прокатила.
А интересно, есть ли другие решения, кроме $a=b^3$ ?