Страниц: [1] 2
  Печать  
Автор Тема: Целочисленные корни уравнения ax^2-by^2=c (без флуда)  (Прочитано 7871 раз)
0 Пользователей и 1 Гость смотрят эту тему.
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
: Октябрь 18, 2010, 07:38:23 �

Новак представил алгоритм определения существования целочисленных корней уравнения вида a*x2-b*y2=c.
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
Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
General
Умник
****
Offline Offline

Сообщений: 681

СПАСИБО
-вы поблагодарили: 47
-вас поблагодарили: 162



Просмотр профиля
Ответ #1 : Октябрь 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

Эти пользователи сказали вам СПАСИБО :

MagTux

За это сообщение 1 пользователь сказал спасибо!
Записан

5 Головоломок | //текст доступен после регистрации//
Новак
Гость
Ответ #2 : Октябрь 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

Эти пользователи сказали вам СПАСИБО :

MagTux

За это сообщение 1 пользователь сказал спасибо!
Последнее редактирование: Октябрь 18, 2010, 10:39:16 от Новак Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #3 : Октябрь 18, 2010, 11:14:28 �

x2=63-y2+(2-3y2)/5

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

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #4 : Октябрь 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 в диапазоне?
Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
General
Умник
****
Offline Offline

Сообщений: 681

СПАСИБО
-вы поблагодарили: 47
-вас поблагодарили: 162



Просмотр профиля
Ответ #5 : Октябрь 18, 2010, 11:21:59 �

А можно поподробнее этот момент? Как видно, что остаток = 4?

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

Эти пользователи сказали вам СПАСИБО :

MagTux

За это сообщение 1 пользователь сказал спасибо!
Записан

5 Головоломок | //текст доступен после регистрации//
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #6 : Октябрь 18, 2010, 11:23:22 �

Прочитал Новака - стало понятно )))
Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
Um_nik
Гость
Ответ #7 : Октябрь 18, 2010, 11:24:23 �

x2=63-y2+(2-3y2)/5

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

Эти пользователи сказали вам СПАСИБО :

MagTux

За это сообщение 1 пользователь сказал спасибо!
Записан
Новак
Гость
Ответ #8 : Октябрь 18, 2010, 11:26:01 �

Тут идёт простой перебор целочисленных значений v в диапазоне?
Да, перебор. Лучшего ничего не придумал Smiley.
Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #9 : Октябрь 18, 2010, 11:50:42 �

2-3y2 делится на 5
3y2 даёт остаток 2
y2 даёт остаток 4
y даёт остаток 2 или 3

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

И вообще приведённые решения основываются на чём либо?
Решение Новака смахивает на алгоритм Евклида. Это он?
Последнее редактирование: Октябрь 18, 2010, 11:56:36 от MagTux Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
Um_nik
Гость
Ответ #10 : Октябрь 18, 2010, 11:56:52 �

В каком смысле теория? Решить в общем случае?
Записан
Новак
Гость
Ответ #11 : Октябрь 18, 2010, 12:08:56 �

Решение Новака смахивает на алгоритм Евклида. Это он?
Нет, это метод спуска, который предполагает сначала последовательное выражение одной переменой чрез другую, пока в представлении переменной не останется дробей, а затем, последовательное «восхождение» по цепочке равенств для получения общего решения уравнения. Хотя линейное уравнение с двумя неизвестными может быть решено с использованием, например, того же алгоритма Евклида.
Вот еще полезная информация:
//текст доступен после регистрации//
примечание: (а,b) - НОД (наиболший общий делитель)

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

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

Эти пользователи сказали вам СПАСИБО :

MagTux

За это сообщение 1 пользователь сказал спасибо!
Последнее редактирование: Октябрь 21, 2010, 15:53:50 от Новак Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #12 : Октябрь 18, 2010, 12:44:48 �

В каком смысле теория? Решить в общем случае?
Ну да.

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

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
Um_nik
Гость
Ответ #13 : Октябрь 18, 2010, 13:02:10 �

= (kc-b)/a , где k - целое число, при котором данное выражение обращается в целое число, k<c
= ((kc-b)/a+mc)^0.5 , где m - целое число, при котором данное выражение обращается в целое число, m<c
Записан
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #14 : Октябрь 18, 2010, 13:24:39 �

Вот я и спрашиваю, это теория какая-то или просто с головы?
Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
Страниц: [1] 2
  Печать  
 
Перейти в: