Решение уравнений в целых числах
Метод бесконечного спуска
жүктеу/скачать 100,62 Kb.
|
aksanova ii. olimpiadnye zadaniya.reshenie uravneniy v tselyh chislah
- Бұл бет үшін навигация:
- 7. Оценка выражений, входящих в уравнение.
- 8. Применение цепных дробей.
- Приложение 1. Таблица остатков при делении степеней (a n :m)
- Приложение 2. Задачи для самостоятельного решения
- Литература
| 6. Метод бесконечного спуска.
Метод спуска предполагает сначала последовательное выражение одной переменой чрез другую, пока в представлении переменной не останется дробей, а затем, последовательное «восхождение» по цепочке равенств для получения общего решения уравнения. Пример 6.1. Решить уравнение в целых числах 5x + 8y = 39. Выберем неизвестное, имеющее наименьший коэффициент , и выразим его через другое неизвестное: . Выделим целую часть: Очевидно, что х будет целым, если выражение окажется целым, что, в свою очередь, будет иметь место тогда, когда число 4 – 3y без остатка делится на 5. Введем дополнительную целочисленную переменную z следующим образом: 4 –3y = 5z. В результате получим уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами. Решать его будем уже относительно переменной y, рассуждая аналогично: . Выделяя целую часть, получим: . Рассуждая аналогично предыдущему, вводим новую переменную u: 3u = 1 – 2z. Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z: = . Требуя, чтобы было целым, получим: 1 – u = 2v, откуда u = 1 – 2v. Дробей больше нет, спуск закончен. Теперь необходимо «подняться вверх». Выразим через переменную v сначала z, потом y и затем x: z = = = 3v – 1; = 3 – 5v. = = 3+8v. Формулы x = 3+8v и y = 3 – 5v, где v – произвольное целое число, представляют общее решение исходного уравнения в целых числах. Ответ: x = 3+8v и y = 3 – 5v. 7. Оценка выражений, входящих в уравнение. Пример 7.1. Решить в целых числах уравнение (х2 + 4)(у2 + 1) = 8ху Решение. Заметим, что если (х ;у ) – решение уравнения, то (-х ;-у ) – тоже решение. И так как х = 0 и у = 0 не являются решением уравнения, то, разделив обе части уравнения на ху, получим: ∙ = 8, (х + )(у + ) = 8. Пусть х > 0, у > 0, тогда, согласно неравенству Коши, х + = 4, у + = 2, тогда их произведение (х + )(у + ) = 4·2 = 8, значит, х + = 4 и у + = 2. Отсюда находим х = 2 и у = 1 – решение, тогда х = -2 и у = -1 – тоже решение. Ответ: (2;1); (-2;-1) Пример 7.2. Решить уравнение в целых числах x2 + 13y2 – 6xy = 100 Решение. x2+13y2–6xy=100 ↔ (x-3y)2+4y2=100. Так как (x-3y)2≥0, то 4y2≤100, или │2y│≤10. Аналогично, в силу 4y2≥0 должно выполняться │x-3y│≤10. Возможны 12 случаев:
Ответ: (±15; ±5); (±10; ±0); (±18; ±4); (±6; ±4); (±17; ±3); (±1; ±3). 8. Применение цепных дробей. Пример 8.1. Решите в целых числах уравнение 25x-18y+1=0. Найдем наибольший общий делитель пары чисел 25 и 18 с помощью цепных дробей, то есть используем один из вариантов алгоритма Евклида. Преобразуем неправильную дробь , последовательно выделяя целые части неправильных дробей: = 1 + = 1 + = 1 + = 1 + = 1 + = 1 + = 1 + , где выражение 1+ называется целой дробью. Числа 1, 2, 1, 1, выделенные в этом выражении, являются последовательными частными алгоритма Евклида для нахождения наибольшего общего делителя пары чисел 25 и18. Отбросим дробь и преобразуем получившуюся цепную дробь в обыкновенную: 1 + – 1 + – . Вычтем полученную дробь из исходной дроби : – = = . Приведем ее к общему знаменателю: 25 ∙ 5 – 18 ∙ 7 + 1 = 0. Получили частное решение исходного уравнения х = 5, у = 7. Общее решение исходного уравнения: х = 5 + 18t; y = 7 + 25t, t Z. Ответ: х = 5+18t; у = 7+25t. Приложение 1. Таблица остатков при делении степеней (an:m)
Приложение 2. Задачи для самостоятельного решения Решить в простых числах уравнение x2 - 2y2 = 1. Доказать, что уравнение x3 + x + 10y = 20004 неразрешимо в целых числах. Доказать, что уравнение x5 + 3x4y - 5x3y2 - 15x2y3 + 4xy4 + 12y5 = 33 неразрешимо в целых числах. Решить в целых числах уравнение 2x3 + xy - 7 = 0. Доказать, что уравнения не имеют целочисленных решений: а) y2 = 5x2 + 6; б) x3 = 2 + 3y2 Решить в целых числах уравнения: а) x2 + x = y4 + y3 + y2 + y; б) x² - y² = 91; в) 2ху = х² + 2y; г) 3x2 +4ху – 7y2 =13 Решите в натуральных числах уравнения: а) 2х² + 5ху – 12у² = 28; б) х² - 4ху – 5у² = 1996. Докажите, что система уравнений не имеет решений в целых числах. Найти все пары целых чисел, удовлетворяющих уравнению а) x2 = y2+ 2y +13; б) xy = 20 – 3x + y; в) xy + 1 = x + y; г) x2– 3xy + 2y2 = 3 Существуют ли целые числа m и n, удовлетворяющие уравнению m2 + 1994 = n2 Найти все простые числа, которые одновременно являются суммой двух простых чисел и разностью двух простых чисел. Докажите, что уравнение x2 – y2 = 30 не имеет решений в целых числах. Решите уравнение x2 – 2х + y2 – 4y + 5 = 0. Если первую цифру трехзначного числа увеличить на n, то полученное число будет в n раз больше исходного. Найдите число n и исходное число. Решить в целых числах уравнение x2 + y2 + z2 = 2xyz. Решить в целых числах уравнение x2 - 2y2 + 8z = 3. Решите в натуральных числах систему уравнений: а) б) Найдите два натуральных числа, разность квадратов которых равна 45. Найдите все пары натуральных чисел, удовлетворяющих уравнению: а) x2 - y2 = 105; б) 2x2 + 5xy – 12y2 = 28 Решите в целых числах уравнение: а) xy + 3x – 5y = – 3; б) x – y = Докажите, что система не имеет целочисленных решений Литература: 1. Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П. Основы теории делимости чисел. Решение уравнений в целых числах. Факультативный курс. – М.: МГИЭТ(ТУ). 2003. – 224 с. 2. В. Серпинский. О решении уравнений в целых числах. 1961. 3. Карпова И.В. Решение уравнений в целых числах. 4. http://www.fmclass.ru/pic/48503321f105d/uravneniya-v-celyh-chislah.pdf Образовательный портал «Физ/Мат класс» www.fmclass.ru. 5. http://diofant.na.by/ 6. www.a-elita.net/userfiles/File/.../Integer%20solutions_2012_10.pdf 7. http://math4school.ru/uravnenija_v_celih_chislah.html жүктеу/скачать 100,62 Kb. Достарыңызбен бөлісу:
|