Методы решений линейных сравнений
Метод перебора рассмотрим на примере.
Например, решим сравнение 6% = 7(mod 5).
Решение. Имеем, а = 6, т = 5.
(6,5) = 1 , следовательно, исходное сравнение имеет единственное решение.
Составим полную систему вычетов по mod 5: 0,1,2,3,4.
Далее перебором проверим все вычеты полной системы:
При х = 0, имеем 6 0 = 7 (mod 5)
6 0-7/f5, следовательно, х= 0 - не является решением.
При х = 1, имеем 61=7 (mod 5)
6- 1-7Z5, следовательно, х = 1 - не является решением.
При х = 2, имеем 6-2 = 7 (mod 5)
6-2 - 7=12 - 7=5 : 5, следовательно, х= 2 - является решением.
Остальные числа полной системы вычетов проверять уже не стоит так как поскольку(6,5)=1, то решение единственное.
Ответ: х = 2(mod 5).
Метод сравнений - метод, основанный на свойствах сравнений
Например, решим сравнение 7х = 8 (mod 13).
Решение. В нашем случае а = 7,т = 13.
Так как (7, 13)=1, то исходное сравнение имеет единственное решение:
- 7х = 8 (mod 13) 7х = 8 + 13 (mod 13)
- 7х = 21 (mod 13) х = 3 (mod 13) Ответ: х = 3 (mod 13).
Метод цепных дробей - метод, основанный на применении цепных дробей.
Например, решим сравнение 5% = 26 (mod 12).
Решение. Имеем а = 5,т = 12.
Так как (5, 12)= 1, то исходное сравнение имеет единственное решение.
_ т 12 „
Представим дробь — = — цепной дробью.
- 12=5-2+2 5=2-2+1 2=1-2
- 12
Следовательно, а0 = 2, аг = 2, а2 = 2, то есть -^-=[2,2,2]
Заполним таблицу:
|
і |
0 |
1 |
2 |
|
|
аі |
2 |
2 |
2 |
|
|
Pi |
1 |
2 |
2-2+l=5 |
5-2+2=12 |
|
Qi |
0 |
1 |
1-2+0=2 |
2-2+1 |
Решение сравнения ах = b(mod т)находим по формуле
х = (—lyPi^btmod т). (2.180)
В нашем случае i=2, следовательно, Р(_х = Рг = 5
Имеем: і = 2,
Pi-i = 5, b = 26, m = 12 x = 5 • 26 (mod 12) x = 130 (mod 12) x = 130- 12 -10 (mod 12) x = 10 (mod 12) Ответ: x = 10 (mod 12).
Метод Эйлера - метод, основанный на применении функции Эйлера. Суть метода такова. Имеем линейное сравнения
а ? х = b(mod т).
Убеждаемся, что (а, т) = 1. Находим решение по формуле
х = b • a(p^~1(mod m). (2.181)
<р(тп) есть функция Эйлера, поэтому и метод решения, линейного сравнения, основанный на формуле
аг • = bx(mod тг)
назовем методом Эйлера.
Например, решим сравнение 3 • х = 4 (mod 34).
Решение. Имеем а = 3,т = 34.
Так как (3, 34) = 1, то исходное сравнение имеет единственное решение: Тогда
х = 4 • З^(34)-1 Раскладываем модуль:
34 = 2-17.
Определяем функцию Эйлера:
<р(34) = (р(2 ? 17) - (2 - 1) • (17 - 1) = 16. Следовательно,
х = 4 • З16-1 (mod 34) х = 4 • З15 (mod 34).
Найдем значение сравнения:
З15(mod 34) = 23 (mod 34) х =4-23 (mod 34) х = 92 (mod 34) x = 24 (mod 34)
Проверка. Подставим найденное решение
х = 24 (mod 34) в исходное уравнение, имеем
(3 ? 24) = (72) = (4)(т. е. = 4(mod 34))
То есть, найденное
х = 24 (mod 34)
есть решение сравнения
3 • х = 4 (mod 34).
Ответ: х = 24 (mod 34).
Метод линейной комбинации - метод, основанный на представлении (а,т) линейной комбинацией.
И так, пусть
а ? х = b(mod т).
Если число т достаточно большое и разложить его на простые множители затруднительно, то необходимо представить (а, т) = 1 в виде линейной комбинации.
1 = а • и + т • V, Тогда
х =bu (modm)
- решение исходного уравнения.
Действительно, умножим обе части этого равенства на Ь: b = a- b- u + m- b- v а • b - и = b(mod т)
x=b u (modm) - решение исходного сравнения а ? х = b(mod m).
(и - коэффициент в линейном представление НОД (а, т) стоящий перед а)
