Вопрос об уравнении в целых числах

[Mathusic]

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

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

[apriv]

Да, существует.

[Mathusic]

apriv в сообщении #599687 писал(а):

Да, существует.

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

[apriv]

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

[Sonic86]

Извиняюсь - не вчитался в вопрос и описал, как решать уравнение в целых числах, если знаем $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$. Такое уравнение мы решать умеем

[nnosipov]

apriv в сообщении #599719 писал(а):

Ежели это эллипс, то грядет конечный перебор.

Опишите, пожалуйста, все натуральные $n$, представимые, например, формой $5x^2+11y^2$.

[apriv]

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

[Mathusic]

Спасибо за полные ответы.

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$

[nnosipov]

apriv в сообщении #599774 писал(а):

Описать все представимые $n$ — это про символ Лежандра задача.

Э, нет, всё гораздо хуже. Гаусс не зря теорию классов и родов бинарных квадратичных форм придумал. Для начала можно посмотреть "Высшую арифметику" Дэвенпорта (гл. 6).

[apriv]

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

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

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

[nnosipov]

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

[apriv]

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

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

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

[nnosipov]

apriv в сообщении #599797 писал(а):

Какой ответ?

Ответ на вопрос, каковы натуральные $n$, представимые формой $5x^2+11y^2$. Можете дать ответ на этот вопрос?

[apriv]

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

apriv в сообщении #599797 писал(а):

Какой ответ?

Ответ на вопрос, каковы натуральные $n$, представимые формой $5x^2+11y^2$. Можете дать ответ на этот вопрос?

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

[nnosipov]

apriv в сообщении #599818 писал(а):

Могу еще раз повторить, что это алгоритмически сводится к вопросу про символ Лежандра

Ваш вопрос про символ Лежандра решается просто, а вот первоначальный вопрос гораздо сложнее. Поэтому не сводится.