Изменения
→Решение линейных систем по модулю
== Решение линейных систем по модулю ==
Пусть <tex> (a, b) = 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> \frac{a}{d}x \equiv \frac{b}{d}(mod \text{ } \frac{m}{d})</tex>,
обозначим его <tex> a_dx \equiv b_d(mod \text{ } m_d)</tex>,. Пусть его решением будет <tex> x \equiv (-1)^x_0 </tex>, тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{n-1}P_{n-1}b_d(mod \text{ } m_d)</tex>, где всего решений будет d. Если нахождение <tex> P_{n-1} x_0 </tex> - не является очевидным, то следует воспользоваться [[Цепная дробь | числитель подходящей дробитеорией цепных дробей]].Пусть , и тогда <tex> P x_0 = (-1)^{n-1}P_{n-1}b_d </tex> <br>После этого решения исходного сравнения запишутся так : , где <tex> x \equiv P; P+m_d; P+2m_d; \ldots ;P+dm_d (mod \textP_{ n-1}m)</tex>- [[Цепная дробь | числитель подходящей дроби]]. === Пример решения ===
