Решить уравнение в целых числах: 107х+84у=1

Предыдущий
вопрос Следующий
вопрос

Для решения данного уравнения в целых числах, можно воспользоваться расширенным алгоритмом Евклида.

Сначала найдем наибольший общий делитель у чисел 107 и 84.
107 = 1 84 + 23
84 = 3 23 + 15
23 = 1 15 + 8
15 = 1 8 + 7
8 = 1 * 7 + 1

Сначала выразим 1 через предыдущие числа:
1 = 8 - 7
1 = 8 - (15 - 8) = 2 8 - 15
1 = 2 (23 - 15) - 15 = 2 23 - 3 15
1 = 2 23 - 3 (84 - 3 23) = 11 23 - 3 84
1 = 11 (107 - 84) - 3 84
1 = 11 107 - 14 * 84

Таким образом, одним из решений уравнения 107x + 84y = 1 будет x = 11, y = -14.

Также имеется бесконечное количество решений, которые можно получить прибавив к x и y кратное 84 и 107 соответственно.