Теоремы о числе решений линейного диофантового уравнения
Приведем здесь формулировки теорем, на основании которых может быть составлен алгоритм решения неопределенных уравнений первой степени от двух переменных в целых числах.
Теорема 1. Если в уравнении (ax + by) = 1, (a,b) = 1, то уравнение имеет, по крайней мере, одно решение.
Теорема 2. Если в уравнении (ax + by) = с , (a,b) = d >1 и с не делится на d , то уравнение целых решений не имеет.
Теорема 3. Если в уравнении (ax + by) = с , (a,b) = d >1 , и d⋮c, то оно равносильно уравнению (a1x + b1y) = 1 , в котором (a1,b1) = 1.
Теорема 4. Если в уравнении (ax + by) = 1, (a,b) = 1, то все целые решения этого уравнения заключены в формулах:
x = x0c + bt
y = y0c - at
где х0 , у0 – целое решение уравнения (ax + by) = 1, t- любое целое число.
Cформулируем на основании этих теорем алгоритм решения уравнения
Алгоритм решения уравнения в целых числах
Сформулированные теоремы позволяют составить следующий алгоритм решения в целых числах уравнения вида (ax + by) = с .
1. Найти наибольший общий делитель чисел a и b ,
если (a,b) = d >1 и с не делится на d , то уравнение целых решений не имеет;
если (a,b) = d >1 и c⋮d , то переходим к этапу 2.
2. Разделить почленно уравнение (ax + by) = с на d, получив при этом уравнение (a1x + b1y) = c1 , в котором (a1,b1) = 1.
3. Найти целое решение (х0 , у0 ) уравнения (a1x + b1y) = 1 путем представления 1 как линейной комбинации чисел a и b ;
4. Составить общую формулу целых решений данного уравнения
x = x0c + bt
y = y0c - at
где х0 , у0 – целое решение уравнения (ax + by) = 1, t- любое целое число.
Способы решения уравнений
При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:
1. Алгоритм Евклида.
2. Способ перебора вариантов.
3. Метод разложения на множители.
4. Метод остатков.
5. Решение уравнений в целых числах как квадратных относительно какой-либо переменной.
6. Цепные дроби.
7. Метод бесконечного спуска.
Пример. Решить уравнение в целых числах 407х – 2816y = 33.
Воспользуемся составленным алгоритмом.
1. Используя алгоритм Евклида, найдем наибольший общий делитель чисел 407 и 2816:
2816 = 407·6 + 374;
407 = 374·1 + 33;
374 = 33·11 + 11;
33 = 11·3
Следовательно (407,2816) = 11, причем 33 делится на 11
2. Разделим обе части первоначального уравнения на 11, получим уравнение 37х – 256y = 3, причем (37, 256) = 1
3. С помощью алгоритма Евклида найдем линейное представление числа 1 через числа 37 и 256.
256 = 37·6 + 34;
37 = 34·1 + 3;
34 = 3·11 + 1
Выразим 1 из последнего равенства, затем последовательно поднимаясь по равенствам будем выражать 3; 34 и полученные выражения подставим в выражение для 1.
1 = 34 – 3·11 = 34 – (37 – 34·1) ·11 = 34·12 – 37·11 = (256 – 37·6) ·12 – 37·11 =
– 83·37 – 256·(–12)
Таким образом, 37·(– 83) – 256·(–12) = 1, следовательно пара чисел х0 = – 83 и у0 = – 12 есть решение уравнения 37х – 256y = 3.
4. Запишем общую формулу решений первоначального уравнения
х = - 83с + bt = -83*3 - 256 t = -249 - 256t
y = -12c - at = -12*3 - 37t = -36 - 37t
где t - любое целое число.
Метод остатков
Пример. Решить в целых числах уравнение:
а) x3 + y3 = 3333333;
б) x3 + y3 = 4(x2y + xy2 + 1).
Решение.
а) Так как x3 и y3 при делении на 9 могут давать только остатки 0, 1 и 8 , то x3+ y3 может давать только остатки 0, 1, 2, 7 и 8. Но число 3333333 при делении на 9 даёт остаток 3. Поэтому исходное уравнение не имеет решений в целых числах.
Ответ: целочисленных решений нет.
б) Перепишем исходное уравнение в виде (x + y)3 = 7(x2y + xy2) + 4. Так как кубы целых чисел при делении на 7 дают остатки 0, 1 и 6, но не 4, то уравнение не имеет решений в целых числах.
Ответ: целочисленных решений нет.