MagTux
Гений-Говорун
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*x 2+8*y 2=317 2) 3*x 2-7*y 2=17
|
|
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
General
Умник
Offline
Сообщений: 681
СПАСИБО
-вы поблагодарили: 47
-вас поблагодарили: 164
|
|
� Ответ #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
|
|
|
|
Новак
Гость
|
|
� Ответ #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
Гений-Говорун
Offline
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #3 : Октябрь 18, 2010, 11:14:28 � |
|
x2=63-y2+(2-3y2)/5
Отсюда y2 даёт остаток 4 при делении на 5
А можно поподробнее этот момент? Как видно, что остаток = 4?
|
|
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
MagTux
Гений-Говорун
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
Сообщений: 681
СПАСИБО
-вы поблагодарили: 47
-вас поблагодарили: 164
|
|
� Ответ #5 : Октябрь 18, 2010, 11:21:59 � |
|
А можно поподробнее этот момент? Как видно, что остаток = 4?
Так тут как Новак подробно расписал: слева число целое, значит и справа должно быть целым. 2-3y 2 делится на 5, такое может быть только если 3y 2 даёт остаток 2, а сам y 2 - 4
|
|
|
|
MagTux
Гений-Говорун
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? 3y 2 дает остаток 2, то есть 12 -> делим на 3 -> y 2 дает остаток 4
|
|
|
|
Новак
Гость
|
|
� Ответ #8 : Октябрь 18, 2010, 11:26:01 � |
|
Тут идёт простой перебор целочисленных значений v в диапазоне? Да, перебор. Лучшего ничего не придумал .
|
|
|
Записан
|
|
|
|
MagTux
Гений-Говорун
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
Гений-Говорун
Offline
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #12 : Октябрь 18, 2010, 12:44:48 � |
|
В каком смысле теория? Решить в общем случае?
Ну да. Если ax 2+b mod c = 0 то ax 2 mod c = c-b x 2 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
Сообщений: 1415
СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99
Реинкарнация Будды
|
|
� Ответ #14 : Октябрь 18, 2010, 13:24:39 � |
|
Вот я и спрашиваю, это теория какая-то или просто с головы?
|
|
|
Записан
|
Существует два правила на пути к успеху: 1. Не говори никому всего, что ты знаешь.
|
|
|
|