1632
правки
Изменения
м
rollbackEdits.php mass rollback
*5. Обе части сравнения можно умножить на одно и тоже число.
** Действительно, из <tex>a \equiv b(mod \text{ } m)</tex>, следует <tex> a = b+mt, ak =bk +mkt </tex>, и, следовательно, <tex>ak \equiv bk(mod \text{ } mk)</tex>.
*6. Обе части сравнения и модуль можно разделить на их общий делитель.
** Следует из пункта "б".
*9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится делиться на это число.
** Следует из пункта "а".
<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_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</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]].
=== Примеры решения ===
Легко находится <tex> x_0 = 2 </tex> <br>
Тогда ответом будет <tex> x_0 =2, x_1 = x_0 - \frac{m}{(a,m)}=-1, x_2 = -4</tex>
'''Пример 2.''' <br>
<tex> 111x \equiv 75(mod \text{ }321)</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>.
