Условие:
Решить линейное сравнение.
a) 15*x =25 mod 28
b) 5*x =80 mod 86
c) 10*x =3 mod 4
Решение:
Решим каждое из линейных сравнений по очереди.
a) 15*x = 25 mod 28
- Приведем уравнение к стандартному виду: 15x - 25 = 28k, где k - целое число.
- Перепишем уравнение: 15x - 28k = 25.
- Найдем наибольший общий делитель (НОД) для 15 и 28. НОД(15, 28) = 1.
- Поскольку НОД(15, 28) делит 25, уравнение имеет решения.
- Найдем обратный элемент к 15 по модулю 28. Для этого используем расширенный алгоритм Евклида:
- 28 = 1*15 + 13
- 15 = 1*13 + 2
- 13 = 6*2 + 1
- 2 = ...