Математика. Тренировка № 2. Уравнения в целых числах. Задания + решения
Алгоритм решения уравнения в целых числах
Сформулированные теоремы позволяют составить следующий алгоритм решения в целых числах уравнения вида (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- любое целое число.