множество, где многочлен вычисляет точный квадрат

[beroal]

Задача. Придумать эффективный алгоритм, который выдаёт все такие $(n, m)$, что $n^2+nm+m^2$ есть точный квадрат (perfect square, квадрат целого числа).

Задача родилась в ходе одного учебного курса по математическому мышлению (другими словами, по практической математической логике). Не знаю, подходит ли она в этот раздел. Там надо было доказать или опровергнуть, что такая пара целых чисел существует. $(0, m)$ и $(n, 0)$ очевидно удовлетворяют условию. Другие пары более интересны.

Очевидный алгоритм: перечислить все пары целых чисел и оставить только те, которые удовлетворяют условию. Этот алгоритм считается неэффективным. Надо лучше.

[gris]

В глаза бросается $(3;5)$. Ну и, конечно, пропорциональные пары $(3k;5k)$. Это я к тому, что пары есть.

[lel0lel]

Имеем $n m=(n+m)^2-a^2$. Пусть $q$ делит $n m$, тогда $$nm=(nm/q)q=\left(\frac{(nm/q)+q}{2}\right)^2-\left(\frac{(nm/q)-q}{2}\right)^2$. Если $(nm/q)+q=2(n+m)$ или $(nm/q)-q=2(n+m)$, тогда n, m решение. Например $m=2 k-1, n=k (k-2)$.
В простых числах кроме уже найденного $3,5$ решений больше нет.

[zhekas]

$n^2+nm+m^2 = z^2$
$4n^2+4nm+4m^2 = (2z)^2$
$(2n+m)^2+3m^2 = (2z)^2$
$(2z)^2-3m^2 = (2n+m)^2$

Если поделить на (2n+m)^2 то получим уравнение Пелля в рациональных числах.
Тогда его параметры выражаются следующими формулами:
2n+m = 3a^2-b^2
m = 2ab
2z = 3a^2+b^2
Или
m=2ab
n=(3a^2-b^2-2ab)/2

Останется только сократить на общий множитель. И готово.

[Shadow]

beroal в сообщении #1254252 писал(а):

ффективный алгоритм, который выдаёт все такие

Все не получится, их бесконечно много. Можно вывести формулу, выдающую все решения (двухпараметрическое решение, уравнение однородное второго порядка), Можно алгоритм, выдающий все в некотором интервале (тогда лучще умный перебор).

[Руст]

$m^2+mn+n^2=(m\theta-n\theta^2)(m\theta^2-n\theta), \ \theta^3=1.$
Это значит эта форма представляет норму чисел из кольца $Z[\theta]$. Степеням из этого кольца соответствуют степени норм, т.е. если брать квадраты в кольце, то их нормы так же будут квадратами.

[lel0lel]

Параметризация
$m=a(2b-a), n=b(b-2a)$
содержит все решения, для которых $(m,n)=1$, т.е. примитивные решения.
Получилось такое тождество
$a^2 (2 b-a)^2-a b (2 a-b) (2 b-a)+b^2 (2 a-b)^2=\left(a^2-a b+b^2\right)^2$

[Sonic86]

Есть общий способ решения подобных задач - метод секущих, изложен в книжке Цфасмана. Делим на квадрат в правой части, получаем уравнение $x^2+xy+y^2=1$ в рациональных числах $x,y$, находим одну рациональную точку, проводим секущую, поскольку уравнение 2-го порядка, то секущая, проходящая через рациональную точку, пересекает кривую в другой рациональной точке. Отсюда все такие точки и находятся.

[scwec]

Эквивалентных рациональных параметрических решений уравнения $m^2+mn+m^2=z^2$ существует бесконечно много.
Интересным, на мой взгляд, является $m=b(b+2a), n=a^2-b^2, z=a^2+ab+b^2$, и вот почему.
Заметим, что справедливо тождество $(m^2+mn+n^2)(a^2+ab+b^2)=r^2+rs+s^2$, где $r=ma-nb, s=na+mb+nb$ и $a,b,m,n$ любые целые числа.
Это тождество позволяет вычислить 2-параметрические решения в целых числах для уравнения $m^2+mn+n^2=z^k$, где $k$ - любое натуральное число.
Так, для $k=3$ это $m=b(a^2+ab+b^2), n=a(a^2+ab+b^2), z= a^2+ab+b^2$,
для $k=4$ это $m=(a^2-b^2)(a^2+4ab+b^2), n=a(a+2b)(2b^2+2ab-a^2), z=a^2+ab+b^2$
для $k=5$ это $m=a(a^4+5ba^3-10ab^3-5b^4), n=(a+b)(ab^3+9a^2{b^2}+ba^3-a^4-b^4)$,
$z=a^2+ab+b^2$ и.т.д.

Этот подход распространяется и на уравнение $x^2+pxy+qy^2=z^k$, где $p,q$ заданные целые числа.

[beroal]

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

Все не получится, их бесконечно много.

Счётное множество. Алгоритм в данном случае есть автомат.

-- Wed Oct 11, 2017 23:08:57 --

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

[beroal]

Насколько я понял, задача не сложная, и для неё есть теория.