2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 множество, где многочлен вычисляет точный квадрат
Сообщение09.10.2017, 15:52 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение09.10.2017, 16:13 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение09.10.2017, 16:57 


20/04/10
1776
Имеем $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$ решений больше нет.

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение09.10.2017, 18:27 


15/03/11
137
$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

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

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение09.10.2017, 18:57 


26/08/11
2057
beroal в сообщении #1254252 писал(а):
ффективный алгоритм, который выдаёт все такие
Все не получится, их бесконечно много. Можно вывести формулу, выдающую все решения (двухпараметрическое решение, уравнение однородное второго порядка), Можно алгоритм, выдающий все в некотором интервале (тогда лучще умный перебор).

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение09.10.2017, 19:31 
Заслуженный участник


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

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение10.10.2017, 00:59 


20/04/10
1776
Параметризация
$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$

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение10.10.2017, 09:46 
Заслуженный участник


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

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение10.10.2017, 21:25 
Заслуженный участник


17/09/10
2132
Эквивалентных рациональных параметрических решений уравнения $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$ заданные целые числа.

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение11.10.2017, 22:12 
Аватара пользователя


17/04/11
658
Ukraine
Shadow в сообщении #1254292 писал(а):
Все не получится, их бесконечно много.

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

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

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

 Профиль  
                  
 
 Re: множество, где многочлен вычисляет точный квадрат
Сообщение11.10.2017, 23:13 
Аватара пользователя


17/04/11
658
Ukraine
Насколько я понял, задача не сложная, и для неё есть теория.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group