175
правок
Изменения
→Решение линейных систем по модулю
== Решение линейных систем по модулю ==
Пусть <tex> (a, bm) = d </tex>. Сравнение <tex> ax \equiv b(mod \text{ }m)</tex> невозможно, если b не делится на '''d'''. При b, кратном '''d''', сравнение имеет '''d''' решений.<br>
'''Поиск решений:'''<br>
<tex> ax \equiv b(mod \text{ }m)</tex>, <tex> (a, b) = d </tex> <br>
обозначим его <tex> a_dx \equiv b_d(mod \text{ } m_d)</tex>. Пусть его решением будет <tex> x_0 </tex>, тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{n-1} - m_d </tex>, всего решений будет d. Если нахождение <tex> x_0 </tex> не является очевидным, то следует воспользоваться [[Цепная дробь|теорией цепных дробей]], и тогда <tex> x_0 = (-1)^{n-1}P_{n-1}b_d</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]].
=== Примеры решения ==='''Пример решения 1.''' <br><tex> 12x \equiv 6(mod \text{ }18)</tex> <br>Найдем НОД <tex>(12,18)=6 </tex> <br>Перейдем к новому сравнению <tex> 2x \equiv 1(3) </tex> <br>Легко находится <tex> x_0 = 2 </tex> <br>Тогда ответом будет <tex> x_0 =2, x_1 =x_0 - \frac{m}{(a,m)}=-1, x_2 =-4</tex>
