2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Вопрос об уравнении в целых числах
Сообщение26.07.2012, 17:32 
Аватара пользователя


14/08/09
1140
Существует ли ответ на следующую задачу:
При каких $n\in \mathbb{N}$ уравнение с целыми коэффициентами $ax^2+bxy+cy^2=n$ имеет целые решения? ($\operatorname{gcd}(a{,}b{,}c)=1$)

Интересует, существование хотя бы алгоритма, выясняющего для произвольного такого уравнения, вопрос на искомый ответ :?

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 18:16 
Заслуженный участник


08/01/12
915
Да, существует.

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 18:47 
Аватара пользователя


14/08/09
1140
apriv в сообщении #599687 писал(а):
Да, существует.

Суховатый ответ :-(
Источником можно поинтересоваться? :?

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 19:16 
Заслуженный участник


08/01/12
915
Ежели это эллипс, то грядет конечный перебор. Ежели гипербола — это уравнение типа Пелля и конечный перебор плюс знание слов «конечно порожденная группа». Ежели парабола — уж как-нибудь можно разобраться, с вырожденными случаями тем более. Ну и посмотрите John H. Conway, Francis Y. C. Fung «The Sensual (Quadratic) Form».

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 19:19 
Заслуженный участник


08/04/08
8504
Извиняюсь - не вчитался в вопрос и описал, как решать уравнение в целых числах, если знаем $a,b,c,n$.

(Оффтоп)

Дирихле Теория чисел - там этот алгоритм на 200 страниц, но несложно. Проще, но недостаточно - Бухштаб и книжки по уравнению Пелля. Есть мощная книжка Гаусса, но там очень много всего. Есть Боревич Шафаревич, но там немного и в общем виде. Есть какая-то очень новая английская книжка по квадратичным формам, но может там не то. да и названия я не помню. :-(
Смысл такой: выделяется полный квадрат (слагаемое с $xy$ исчезает) - получается знакопостоянная форма или знакопеременная. В случае знакопостоянной формы - тупо перебор, и вроде как вряд ли оптимизируемый. Например, число решений уравнения $x^2+y^2=N$ прямо связано с факторизацией $N$, что характеризует сложность задачи. В случае знакопеременной формы получаем обобщенное уравнение Пелля, которое Вы знаете как решать - ищем единицу, ищем частное решение и строим общее решение. Существование частного решения сводится (если не вру) к существованию решения некоторого сравнения.
Гуглите наконец.

apriv в сообщении #599719 писал(а):
Ежели парабола — уж как-нибудь можно разобраться, с вырожденными случаями тем более.
А вроде как однородная форма дана, так что параболы нету. Кстати, параболический случай с ограничением натуральнозначности переменных - какая-то $NP$-задача (в Гэри Джонсоне есть)

-- Чт июл 26, 2012 16:35:07 --

Sonic86 в сообщении #599721 писал(а):
А вроде как однородная форма дана, так что параболы нету.
Вру, парабола есть, но это будет $t^2=A$. Такое уравнение мы решать умеем :-)

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 20:12 
Заслуженный участник


20/12/10
6549
apriv в сообщении #599719 писал(а):
Ежели это эллипс, то грядет конечный перебор.
Опишите, пожалуйста, все натуральные $n$, представимые, например, формой $5x^2+11y^2$.

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 20:25 
Заслуженный участник


08/01/12
915
Я про ответ при фиксированном $n$ говорил, действительно. Описать все представимые $n$ — это про символ Лежандра задача.

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 20:35 
Аватара пользователя


14/08/09
1140
Спасибо за полные ответы.

apriv в сообщении #599719 писал(а):
Ежели парабола — уж как-нибудь можно разобраться...

А как будет выглядеть парабола, например? Что-то я туплю :?

Sonic86 в сообщении #599721 писал(а):
Смысл такой: выделяется полный квадрат (слагаемое с $xy$ исчезает)

То есть делаются линейные замены с коэф-тами из $\mathbb{Z}$.

Но задача не такая немного. Вот есть, к примеру, уравнение
$$2x^2+xy+y^2=n$$
Ну вот приведем к виду $11x^2+(y+2x)^2=4n$ - эллиптический тип, так. Для конкретного $n$ можем даже решить. Но как описать "хорошо" все $n$ при которых есть решение?

===
Upd. (добавлено при предпросмотре сообщения, когда появились новые посты)
nnosipov как раз правильно понял, что я хотел спросить.

apriv в сообщении #599774 писал(а):
Я про ответ при фиксированном $n$ говорил, действительно. Описать все представимые $n$ — это про символ Лежандра задача.

Для некоторых уравнений описание можно найти.
А я, собственно, и хотел поинтересоваться для случая произвольного $n$ :?

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 20:41 
Заслуженный участник


20/12/10
6549
apriv в сообщении #599774 писал(а):
Описать все представимые $n$ — это про символ Лежандра задача.
Э, нет, всё гораздо хуже. Гаусс не зря теорию классов и родов бинарных квадратичных форм придумал. Для начала можно посмотреть "Высшую арифметику" Дэвенпорта (гл. 6).

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 20:46 
Заслуженный участник


08/01/12
915
nnosipov в сообщении #599789 писал(а):
]Э, нет, всё гораздо хуже. Гаусс не зря теорию классов и родов бинарных квадратичных форм придумал. Для начала можно посмотреть "Высшую арифметику" Дэвенпорта (гл. 6).

Ну да, но для сведения к приведенному случаю есть алгоритм, после которого и остается вопрос про символ Лежандра.

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 20:49 
Заслуженный участник


20/12/10
6549
apriv, и какой же ответ для формы $5x^2+11y^2$?

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 20:55 
Заслуженный участник


08/01/12
915
nnosipov в сообщении #599794 писал(а):
apriv, и какой же ответ для формы $5x^2+11y^2$?

Какой ответ? Говорю же, что остается не ответ, а вопрос про символ Лежандра — по каким модулям $-4\cdot 5\cdot 11$ является квадратичным вычетом.

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 21:06 
Заслуженный участник


20/12/10
6549
apriv в сообщении #599797 писал(а):
Какой ответ?
Ответ на вопрос, каковы натуральные $n$, представимые формой $5x^2+11y^2$. Можете дать ответ на этот вопрос?

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 21:16 
Заслуженный участник


08/01/12
915
nnosipov в сообщении #599810 писал(а):
apriv в сообщении #599797 писал(а):
Какой ответ?
Ответ на вопрос, каковы натуральные $n$, представимые формой $5x^2+11y^2$. Можете дать ответ на этот вопрос?

Могу еще раз повторить, что это алгоритмически сводится к вопросу про символ Лежандра — см. выше, и можно что-то узнать про разложение $n$ на простые множители. Я же не говорил, что могу дать ответ на этот вопрос в разумном виде.

 Профиль  
                  
 
 Re: Вопрос об уравнении в целых числах
Сообщение26.07.2012, 21:22 
Заслуженный участник


20/12/10
6549
apriv в сообщении #599818 писал(а):
Могу еще раз повторить, что это алгоритмически сводится к вопросу про символ Лежандра
Ваш вопрос про символ Лежандра решается просто, а вот первоначальный вопрос гораздо сложнее. Поэтому не сводится.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

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



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

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


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

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