Форум умных людей

Задачи и головоломки => Помогите решить! => Тема начата: MagTux от Октябрь 18, 2010, 07:38:23



Название: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 07:38:23
Новак представил алгоритм определения существования целочисленных корней уравнения вида a*x2-b*y2=c (http://nazva.net/forum/index.php/topic,4560.msg93341.html#msg93341).
ax^2 – by^2 = c , a,b,c – цілі. Нехай x^2 = n  y^2 = m , звідки an – bm = cдіофантове рівняння 1-ї степені з двома не відомими.

Теорема. Якщо в рівнянні an – bm = c , НСД( a , b) = 1 , то всі цілі розв’язки цього рівняння описують формули: n = n0c – bt , m = m0c – at , де n0 , m0 – цілий розв’язок рівняння an – bm = 1 , t – довільне ціле число.

Для 3x^2 – 2y^2 = 270 та 3x^2 – 2y^2 = 2160  НСД( 3 , 2 ) = 1. Згідно теореми маємо розв’язки цих рівнянь:
x^2 = c – 2t , y^2 = c – 3t, де с = 270 і 2160; t – довільне ціле.

Щоб при спільному t  x та y були цілими, необхідно, щоб c > = 3t > = 2t , причому, якщо с – наприклад, не просте і представляється як с = d13^i = d22^j , де i , j > = 0, d1 , d2 > 1 - цілі, тоді:
(d1 = 1 або, ділячись на 3, дає остачу 1) і (d2 = 1 або, ділячись на 2, дає остачу 1).

270 = 10*3^3, 10 = 3*3 + 1
270 = 135*2^1, 135 = 67*2 + 1
При с = 270 цілий розв’язок існує

2160 = 80*3^3, 80 = 26*3 + 2
2160 = 135*2^4, 135 = 67*2 + 1
При с = 2160 цілий розв’язок не існує

Якось так...
Но, признаюсь, я так и не понял, как найти целочисленные корни.

Давайте ещё раз на примерах.
Найти целочисленные корни (хотя-бы одну пару) уравнений:
1) 5*x2+8*y2=317
2) 3*x2-7*y2=17


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: General от Октябрь 18, 2010, 10:28:42
Первое я решал так
Записал его в виде:
x2=63-y2+(2-3y2)/5

Отсюда y2 даёт остаток 4 при делении на 5, а у, соответственно, 3 или 2. Пробуем у=2, тогда х2=63-4-2=57 - не является полным квадратом. А вот при у=3 х=7.

Второе:
x2=5+2y2+(2+y2)/3
Тут перебрать побольше потребовалось, но получен результат
х=8, у=5


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Новак от Октябрь 18, 2010, 10:35:00
1) 5*x2+8*y2=317

n= x^2, m= y^2 => 5n+8m=317 ((1))

1. Выберем неизвестное, имеющее наименьший коэффициент (в нашем случае это n ), и выразим его через другое неизвестное: n=(317-8m)/5.  Выделим целую часть: n=(315+2-3m-5m)/5=(315-5m+2-3m)/5=63-m+(2-3m)/5. Очевидно, что n будет целым, если выражение (2-3m)/5 окажется целым, что, в свою очередь, будет иметь место тогда, когда число 2-3m без остатка делится на 5. 

2. Введем дополнительную целочисленную переменную z следующим образом: 2-3m = 5z. В результате получим уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами. Решать его будем уже относительно переменной m, рассуждая точно также как в п.1: m=(2-5z)/3. Выделяя целую часть, получим: m=(3-1-2z-3z)/3=(3-3z-(1+2z))/3=1-z-(1+2z)/3 . Рассуждая аналогично предыдущему, вводим новую переменную u: 3u = 1+2z.

3. Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z: z=(3u-1)/2=(2u+u-1)/2=u+(u-1)/2 . Требуя, чтобы  (u-1)/2 было целым, получим: u-1=2v, откуда u= 1+2v. Дробей больше нет, спуск закончен.

4. Теперь необходимо «подняться вверх». Выразим через переменную v сначала z, потом n и затем m:
z= u+(u-1)/2=1+2v+(1+2v-1)/2=1+2v+v=1+3v
m=1-z-(1+2z)/3=1-(1+3v)-(1+2(1+3v))/3=-3v-(1+2+6v)/3=-3v-1-2v=-5v-1
n=63-m+(2-3m)/5=63-(-5v-1)+(2-3(-5v-1))/5=63+5v+1+(2+15v+3)/5=64+5v+1+3v=8v+65

5. Формулы n=65+8v  и m=-1-5v, где v – произвольное целое число, представляют общее решение исходного уравнения ((1)) в целых числах.

6. Для x^2=65+8v и y^2=-1-5v  v должно быть: -8=<v<0

Когда v=-2:
x^2=65+8v=65-16=49=7^2, x=7
y^2=-1-5v=-1+10=9=3^2, y=3

Ответ: x=7, y=3


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 11:14:28
x2=63-y2+(2-3y2)/5

Отсюда y2 даёт остаток 4 при делении на 5
А можно поподробнее этот момент? Как видно, что остаток = 4?


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 11:18:57
6. Для x^2=65+8v и y^2=-1-5v  v должно быть: -8=<v<0
Когда v=-2:
x^2=65+8v=65-16=49=7^2, x=7
y^2=-1-5v=-1+10=9=3^2, y=3
Ответ: x=7, y=3
Тут идёт простой перебор целочисленных значений v в диапазоне?


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: General от Октябрь 18, 2010, 11:21:59
А можно поподробнее этот момент? Как видно, что остаток = 4?

Так тут как Новак подробно расписал: слева число целое, значит и справа должно быть целым.  2-3y2 делится на 5, такое может быть только если 3y2 даёт остаток 2, а сам y2 - 4


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 11:23:22
Прочитал Новака - стало понятно )))


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Um_nik от Октябрь 18, 2010, 11:24:23
x2=63-y2+(2-3y2)/5

Отсюда y2 даёт остаток 4 при делении на 5
А можно поподробнее этот момент? Как видно, что остаток = 4?
3y2 дает остаток 2, то есть 12 -> делим на 3 -> y2 дает остаток 4


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Новак от Октябрь 18, 2010, 11:26:01
Тут идёт простой перебор целочисленных значений v в диапазоне?
Да, перебор. Лучшего ничего не придумал :).


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 11:50:42
2-3y2 делится на 5
3y2 даёт остаток 2
y2 даёт остаток 4
y даёт остаток 2 или 3

Существует ли какая-либо теория по раскручиванию таких цепочек остатков от деления? Т.е. какой-нибудь принцип, по которому легко можно найти все остатки от деления?

И вообще приведённые решения основываются на чём либо?
Решение Новака смахивает на алгоритм Евклида. Это он?


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Um_nik от Октябрь 18, 2010, 11:56:52
В каком смысле теория? Решить в общем случае?


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Новак от Октябрь 18, 2010, 12:08:56
Решение Новака смахивает на алгоритм Евклида. Это он?
Нет, это метод спуска, который предполагает сначала последовательное выражение одной переменой чрез другую, пока в представлении переменной не останется дробей, а затем, последовательное «восхождение» по цепочке равенств для получения общего решения уравнения. Хотя линейное уравнение с двумя неизвестными может быть решено с использованием, например, того же алгоритма Евклида.
Вот еще полезная информация:
(http://s005.radikal.ru/i209/1010/6f/734d262c8045.jpg) (http://www.radikal.ru)
примечание: (а,b) - НОД (наиболший общий делитель)

Теорема 5.5.. Разность целых чисел а и b делится на натуральное число m в том и только в том случае, когда числа а и b при делении на m дают одинаковые остатки.
Замечание. Такие числа называют еще равноостаточными, или сравнимыми по модулю m.

Теорема 5.6. (алгоритм Эвклида). Пусть a и b – два целых числа,  b<>0 и a=bq+r, 0=<r<|b|,   тогда   (a,b)=(b,r).


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 12:44:48
В каком смысле теория? Решить в общем случае?
Ну да.

Если
ax2+b mod c = 0
то
ax2 mod c = c-b
x2 mod c = ?
x mod c = ?


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Um_nik от Октябрь 18, 2010, 13:02:10
= (kc-b)/a , где k - целое число, при котором данное выражение обращается в целое число, k<c
= ((kc-b)/a+mc)^0.5 , где m - целое число, при котором данное выражение обращается в целое число, m<c


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 13:24:39
Вот я и спрашиваю, это теория какая-то или просто с головы?


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Um_nik от Октябрь 18, 2010, 13:48:57
Про теории у Генерала или у Новака спрашивай, я все просто так решаю)))


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 18, 2010, 13:56:40
Про теории у Генерала или у Новака спрашивай, я все просто так решаю)))
А я вроде на форум пишу, а не тебе в личку. ;)
Просто так решать нельзя. Решение должно быть основано на правилах, теоремах и т.п.


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Um_nik от Октябрь 18, 2010, 13:59:23
Да я и говорю, что я теорему не знаю.

Некоторые теоремы я помню, некоторые чувствую))) Но ни те, ни другие не могу строго описать. Т.е. формулировки я не знаю.


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Новак от Октябрь 18, 2010, 15:18:27
И вообще приведённые решения основываются на чём либо?
Теория есть. Я сводил условие к неоднородному Диофантовому уравнению первой степени с двумя неизвестными и пользовался одним из методов, который ей присущ. Трудами П. Ферма, Дж. Валлиса, Л. Эйлера, Ж. Лагранжа и К. Гаусса были исследованы Диофантовы уравнения вида ах^2 + bxy + су^2 + dx + еу + f = 0, где а, b, с, d, е, f — целые числа, т. е. общее неоднородное уравнение второй степени с двумя неизвестными. Ферма утверждал, например, что Диофантовы уравнения x^2 — dy^2 = 1 (уравнение Пелля), где d — целое положительное число, не являющееся квадратом, имеет бесконечно много решений. Валлис и Эйлер дали способы решения этого уравнения, а Лагранж доказал бесконечность числа решений. С помощью непрерывных дробей Лагранж исследовал общее неоднородное Диофантово уравнение второй степени с двумя неизвестными. В инэте вряд ли такое найдешь, попробуй поискать в городской библиотеке.

Решение неопределенных уравнений первой степени от двух  переменных в целых числах:
Многие «математические фокусы» основаны на методах решения неопределенных уравнений. Например, фокус с угадыванием даты рождения. Предложите Вашему знакомому угадать его день рождения по сумме чисел равных произведению даты его рождения на 12 и номера месяца рождения на 31. Для того чтобы угадать день рождения Вашего знакомого нужно решить уравнение: 12х + 31y = А.  Пусть Вам назвали число 380, т.е. имеем уравнение 12х + 31y = 380. Для того чтобы найти х и y можно рассуждать так: число 12х + 24y делится на 12, следовательно, по свойствам делимости (теорема 5.5.), числа 7y и 380 должны иметь одинаковые остатки при делении на 12. Число 380 при делении на 12 дает остаток 8, следовательно 7y при делении на 12 тоже должно давать в остатке 8, а так как y - это номер месяца, то  1 ≤ y ≤ 12, следовательно y = 8. Теперь нетрудно найти х = 11. Таким образом, Ваш знакомый родился 11 августа.


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: General от Октябрь 20, 2010, 08:31:07
Просто так решать нельзя. Решение должно быть основано на правилах, теоремах и т.п.

Должно, конечно. Но просто со временем развивается чутьё, позволяющее в явном виде не формулировать используемые методы.

А собственно по методам в англоязычной Википедии про Diophantine equation (http://en.wikipedia.org/wiki/Diophantine_equation) много написано.


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: MagTux от Октябрь 20, 2010, 09:15:20
Должно, конечно. Но просто со временем развивается чутьё, позволяющее в явном виде не формулировать используемые методы.
Абсолютно согласен, но когда решение задачи объясняешь другому человеку, то своё чутьё тяжело передать. Тем более чужому чутью тяжелее верится, нежели теоремам.


Название: Re: Целочисленные корни уравнения ax^2-by^2=c (без флуда)
Отправлено: Goha от Январь 05, 2011, 20:30:24
Уже давно мечтал научиться решать чтот вроде этого. диофантовые уравнения часто встречаются в олимпиадах а как вам вот это уравнение x^2-y^2=1998*k где k простое