Целые точки на кривых второго порядка.

[мат-ламер]

Спасибо!

[pronix]

AKM, спасибо большое за коррекцию, так сойдёт . Хорхе, спасибо за ссылку, никогда не слышал про эту книгу. Жаль, что нет в свободном виде на русском, но хоть на английском почитаю.
мат-ламер, книги Гельфонда и Серпинского смотрел, про уравнения Пелля тоже читал, но, как вы правильно заметили, там нет решения моей задачи, а только некоторые частные случаи. Сейчас посмотрю книгу Острик и Цфасман - Алгебраическая геометрия и теория чисел. Может поможет.

[maxal]

pronix в сообщении #350910 писал(а):

а существует ли общее решение для уравнений вида $ax^2+by^2+cxy+dx+ey+f=0$,

Линейными заменами оно сводится к к уравнению Пелля-Ферма - а далее см. topic29053.html

Кроме того, есть ява-апплет, решающий такие уравнения для заданных коэффициентов:
Quadratic two integer variable equation solver

[pronix]

maxal, спасибо, но, как мне кажется, здесь собака глубже зарыта. Возьмём и разберём, к примеру, "страшное" уравнение, которое я писал выше, а именно:
$6x^2+6xy+12x+7y-31272=0$(1).
Преобразуем его к виду
$ap^2+2bpq+cq^2=M$ (т.е. к форме).
Умножим правую и левую части уравнения (1) на 2, чтобы все коэффициенты были чётны (это удобно для преобразования). Получим
$12x^2+12xy+24x+14y-62544=0$.
Далее вводим замены:
$p=(b^2-ac)x+be-cd$
$q=(b^2-ac)y+bd-ae$.
Очевидно, что $a=12, b=6, c=0, d=12, e=7, f=-62544$.
Находим представление формы M
$-M=f(b^2-ac)^2+(b^2-ac)(ae^2-2bde+cd^2)$.
После подстановки коэффициентов и упрощения получим следующее
$p=36x+42$
$p=36y-12$
$M=81072144$.
Само уравнение $p^2+pq=6756012$ или же
$(6x+7)(6x+6y+5)=187667$
Как уже писал выше, очень неудобно искать простые делители больших чисел (данное число ещё не трудно разложить, а вот если взять больше, то начинаются проблемы и без электроники никуда ).
Далее форму $p^2+pq=6756012$ привожу к каноническому виду и далее к уравнению Пелля-Ферма.
У меня получилось такое уравнение
$t^2-p_1^2=6756012(1+\sqrt{2} )$, где $t=\frac{2+\sqrt{2}}{2}q_1$. Дискриминант формы равен квадрату ($D=1$). И тут самое интересное. В книге Henri Cohen "Number Theory: Volume I: Tools and Diophantine Equations" (стр.375) написано, что, если дискриминант равен квадрату, то цитирую: "if $D = d^2$ the
equation can be written (x - dy$)(x + dy$) = $N$, so it is only a matter of
listing all (positive or negative) divisors $g$ of $N$ such that $g +N/g$ is even
and $ d | (N/g − g)$-g)". Т.е. опять надо разлогать свободный член на простые множители. Посему, проблема остаётся открытой.
P.S. ява апплет это хорошо, я и сам могу написать программу, которая тоже будет решать уравнения, но это для проверки...для меня по крайней мере. Не хочется, чтобы задачи подобного рода были решаемы только с помощью компьютеров. Вот, к примеру, проблему четырёх красок решили, но ничего красивого в решении нет...просто перебор на мощном компьютере.

[ИСН]

Значит, это одна из задач, сложность которых привязана к сложности факторизации больших чисел. Было бы странно, если бы это удалось обойти.

[pronix]

ИСН, как бы я не хотел этого, но придётся согласиться с вами, потому что я даже приблизительно не вижу решения данной задачи (при любых, сколь угодно больших коэффициентах) без применения компьютера.

[maxal]

pronix в сообщении #354684 писал(а):

Т.е. опять надо разлогать свободный член на простые множители. Посему, проблема остаётся открытой.

А вы что хотели?! Решение даже простейшего уравнения $x^2 - y^2=N$ равносильно факторизации $N$, что составляет по сути основу метода факторизации Ферма и многих других.

Обычно при решении диофантовых уравнений предполагается, что с целыми числами мы умеем делать всё (в том числе и разлагать на множители). Это впрочем, стандартный подход в математике (в отличие от компьютерных наук) - если что-то существует, то мы можем это что-то использовать. Разложение числа на простые существует - значит, мы его можем использовать.

[мат-ламер]

maxal в сообщении #354585 писал(а):

pronix в сообщении #350910 писал(а):

а существует ли общее решение для уравнений вида $ax^2+by^2+cxy+dx+ey+f=0$,

Линейными заменами оно сводится к к уравнению Пелля-Ферма - а далее см. topic29053.html

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

[maxal]

мат-ламер в сообщении #354875 писал(а):

А насколько правомерны тут произвольные линейные замены? Ведь нужно переводить целые решения в целые и наоборот.

Коэффициенты в замене переменных всегда можно сделать целыми, домножая все уравнение на подходящее целое число. Тогда целые решения исходного уравнения перейдут в целые решения преобразованного. Вот обратное, к сожалению, неверно - решения преобразованного уравнения придется "просеивать", чтобы найти решения исходного.

[pronix]

Цитата:

А вы что хотели?! Решение даже простейшего уравнения $x^2-y^2=N$ равносильно факторизации , что составляет по сути основу метода факторизации Ферма и многих других.

Обычно при решении диофантовых уравнений предполагается, что с целыми числами мы умеем делать всё (в том числе и разлагать на множители). Это впрочем, стандартный подход в математике (в отличие от компьютерных наук) - если что-то существует, то мы можем это что-то использовать. Разложение числа на простые существует - значит, мы его можем использовать.

Это я понимаю, но ведь согласитесь, что такой подход не всегда действует. Поэтому я и задался таким вопросом (о решение вышеописанных уравнений без перебора). Интересно, а существует вообще метод (теоретически хотя бы), который бы убрал зависимость сложности данных уравнений от сложности факторизации больших чисел? Доказательство этого я ещё не встречал (ведь отрицательный ответ тоже ответ).

[Ales]

Решение уравнения $ax^2+by=c$ в целых положительных - NP-полная задача.
(Нахождение целых положительных точек на параболе).

И вся математика может быть в некотором смысле сведена к этому вопросу.

Хотя найти целую, не обязательно натуральную точку на параболе довольно "просто": достаточно уметь раскладывать число на множители.

-- Ср сен 22, 2010 09:28:20 --

Еще есть алгоритм (Лежандр, Гаусс) для решения $ax^2+by^2=c$ в дробях.
То есть для решения в целых $ax^2+by^2=cz^2$.

-- Ср сен 22, 2010 10:08:34 --

мат-ламер в сообщении #354875 писал(а):

maxal в сообщении #354585 писал(а):

pronix в сообщении #350910 писал(а):

а существует ли общее решение для уравнений вида $ax^2+by^2+cxy+dx+ey+f=0$,

Линейными заменами оно сводится к к уравнению Пелля-Ферма - а далее см. topic29053.html

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

Если есть решение $ax^2+by^2+cxy=1$, то уравнение можно привести к виду:
$x^2 (+xy)+By^2 (+x) +Ey+F=0$.
Думаю, что кроме этого ничего сделать нельзя (не уверен).

-- Ср сен 22, 2010 10:09:38 --

Но конечно решение, приводящее форму к единице есть не всегда.

[maxal]

pronix в сообщении #355004 писал(а):

Интересно, а существует вообще метод (теоретически хотя бы), который бы убрал зависимость сложности данных уравнений от сложности факторизации больших чисел? Доказательство этого я ещё не встречал (ведь отрицательный ответ тоже ответ).

Не существует. Доказательство я уже вам указал: решение уравнения $x^2 - y^2=N$ равносильно факторизации $N$. Другими словами, задача решения квадратных диофантовых уравнений от двух переменных никак не проще задачи факторизации.

[Ales]

maxal в сообщении #355128 писал(а):

pronix в сообщении #355004 писал(а):

Интересно, а существует вообще метод (теоретически хотя бы), который бы убрал зависимость сложности данных уравнений от сложности факторизации больших чисел? Доказательство этого я ещё не встречал (ведь отрицательный ответ тоже ответ).

Не существует. Доказательство я уже вам указал: решение уравнения $x^2 - y^2=N$ равносильно факторизации $N$. Другими словами, задача решения квадратных диофантовых уравнений от двух переменных никак не проще задачи факторизации.

Если надо найти хотя бы одно решение, а не все, факторизация в данном примере не нужна. Поэтому это не совсем тривиальный вопрос.

[maxal]

Ales в сообщении #355140 писал(а):

Если надо найти хотя бы одно решение, а не все

Под "решением уравнения" в математике подразумевается нахождение всех его решений.

[pronix]

maxal, спасибо за развёрнутый ответ.

Цитата:

Если надо найти хотя бы одно решение, а не все, факторизация в данном примере не нужна. Поэтому это не совсем тривиальный вопрос.

А вот это уже интересно (для меня по крайней мере)! Ales, можете пояснить? Т.е. получается, что существует метод, который не зависит от сложности факторизации больших чисел? Как я уже писал выше, сейчас решаю одну задачу и дошёл до этапа, когда нужно найти корни уравнения второй степени от двух неизвестных в целых числах. Общего случая нет, но мне очень облегчит дальнейшее продвижении в решении задачи хотя бы знание того, что у уравнения есть хотя бы одна пара целых кореней ($x;y$). Если знаете такой метод, то примените его к уравнению (т.е. покажите, имеет оно целые корни или нет)
$6x^2+6xy+12x+7y-31272=0$. Буду очень признателен.