Изменения

Пусть <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)^{n-1}P_{n-1}b_d(mod \text{ } m_d)</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]].Пусть <tex> P = (-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 \text{ }m)</tex>