Изменения

** Действительно, из <tex>a \equiv b(mod \text{ } m)</tex>, следует <tex> a = b+mt, ak =bk +mkt </tex>, и, следовательно, <tex>ak \equiv bk(mod \text{ } mk)</tex>.

*9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится делиться на это число.

Пусть <tex> (a, bm) = d </tex>. Сравнение <tex> ax \equiv b(mod \text{ }m)</tex> невозможно, если b не делится на '''d'''. При b, кратном '''d''', сравнение имеет '''d ''' решений.<br>'''Поиск решений:'''<br>

обозначим его <tex> a_dx \equiv b_d(mod \text{ } m_d)</tex>,. Пусть его решением будет <tex> x \equiv x_0 </tex>, тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{n-1} - m_d </tex>(следует понимать, что <tex> x_i </tex> вычет по модулю, поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение <tex> x_0 </tex> не является очевидным, то следует воспользоваться [[Цепная дробь|теорией цепных дробей]], и тогда <tex> x_0 = (-1)^{n-1}P_{n-1}b_d(mod \text{ } m_d)</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]].Пусть === Примеры решения ==='''Пример 1.''' <br><tex> 12x \equiv 6(mod \text{ }18)</tex> <br>Найдем НОД <tex> P (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 -1)^\frac{n-1m}P_{n(a,m)}=-1}b_d , x_2 = -4</tex>  '''Пример 2.''' <br>После этого решения исходного сравнения запишутся так : <tex> x 111x \equiv P; P+m_d; P+2m_d; \ldots ;P+dm_d 75(mod \text{ }m321)</tex> <br>Найдем НОД <tex>(111,321)=3 </tex>, 75 кратно 3, значит имеем 3 решения <br>Перейдем к новому сравнению <tex> 37x \equiv 25(107) </tex> <br>Воспользуемся цепными дробями, в нашем случае <tex> n=4, p_{n-1} = 26</tex>, значит <tex> x_0 \equiv -26\cdot 25 (107) \equiv 99(107)</tex><br>Тогда ответом будет <tex> x_0 = 99, x_1 = 206, x_2 = 313 </tex>.