Решение уравнений в целых числах
Способ перебора вариантов
жүктеу/скачать 100,62 Kb.
|
aksanova ii. olimpiadnye zadaniya.reshenie uravneniy v tselyh chislah
- Бұл бет үшін навигация:
- 2. Применение алгоритма Евклида. Теорема.
| 1. Способ перебора вариантов.
Пример 1.1. Найти множество всех пар натуральных чисел, которые являются решениями уравнения 49х + 51у = 602. Решение. Выразим из уравнения переменную х через у х = , так как х и у – натуральные числа, то х = 602 - 51у ≥ 49, 51у≤553, 1≤у≤10 . Полный перебор вариантов показывает, что натуральными решениями уравнения являются х=5, у=7. Ответ: (5;7). 2. Применение алгоритма Евклида. Теорема. Дано уравнение ax+by=c, где a, b, c-целые числа, a и b не равны 0. Теорема: Если c не делится нацело на НОД(a,b), то уравнение не разрешимо в целых числах. Если НОД(a,b)=1или c делится на НОД(a,b), то уравнение разрешимо в целых числах. Если (x0, y0 )- какое-нибудь решение уравнения, то все решения уравнения задаются формулами: x=x0-bt y=y0+at , где t- принадлежит множеству целых чисел. Пример 2.1. Решить уравнение в целых числах 5х + 7у = 19 Подберём сначала некоторое конкретное решение. В данном случае, это просто, например, x0 = 1, y0 = 2. Тогда 5x0 + 7y0 = 19, откуда 5(х – x0) + 7(у – y0) = 0, 5(х – x0) = –7(у – y0). Поскольку числа 5 и 7 взаимно простые, то х – x0 = 7k, у – y0 = –5k. Значит, общее решение: х = 1 + 7k, у = 2 – 5k, где k – произвольное целое число. Ответ: (1+7k; 2–5k), где k – целое число. Пример 2.2. Решить уравнение 201х – 1999у = 12. Найти некоторое конкретное решение подбором в данном случае достаточно сложно. Воспользуемся алгоритмом Евклида для чисел 1999 и 201: НОД(1999, 201) = НОД(201, 190) = НОД(190, 11) = НОД(11, 3) = НОД(3 , 2) = НОД(2, 1) = 1. Запишем этот процесс в обратном порядке: 1 = 2 – 1 = 2 – (3 – 2) = 2·2 – 3 = 2· (11 – 3·3) – 3 = 2·11 – 7·3 = 2·11 – 7(190 – 11·17) = = 121·11 – 7·190 = 121(201 – 190) – 7·190 = 121·201 – 128·190 = = 121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999. Значит, пара (1273, 128) является решением уравнения 201х – 1999у = 1. Тогда пара чисел x0 = 1273·12 = 15276, y0 = 128·12 = 1536 является решением уравнения 201х – 1999у = 12. Общее решение этого уравнения запишется в виде х = 15276 + 1999k, у = 1536 + 201k, где k – целое число, или, используя, что 15276 = 1283 + 7·1999, 1536 = 129 + 7·201, имеем х = 1283 + 1999n, у = 129 + 201n, где n – целое число. Ответ: (1283+1999n, 129+201n), где n – целое число. жүктеу/скачать 100,62 Kb. Достарыңызбен бөлісу:
|