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 – целое число.
