175
правок
Изменения
Нет описания правки
<tex>a \equiv b(mod \text{ } m)</tex> <br><br>
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
*1а. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t {{---}} целое.*2б. Делимости <tex>\Huge{a - b}</tex> на '''m'''.
** Действительно, из <tex> a \equiv b(mod \text{ } m) </tex> следует <tex> a = mq + r, \text{ } b = mq_1 + r </tex>, откуда <tex> a - b = m(q-q_1)</tex>, и <tex> a = b + mt</tex>, где <tex> t = q - q_1</tex>.<br>
** Обратно, из <tex>\Huge{a = b + mt}</tex>, представляя '''b''' в форме <tex> b = mq_1 + r </tex>, выводим <tex> a = mq + r </tex>, где <tex> q = q_1 + t </tex>, значит <tex> a \equiv b(mod \text{ } m) </tex>.
=== Свойства сравнений ===
*1. Два числа, сравнимые с третьим сравнимы между собой. <tex>a \equiv c(mod \text{ }m) \text{, } b \equiv c(mod \text{ }m) \Rightarrow a \equiv b(mod \text{ }m)</tex>
** Легко выводится из пункта "а".
*2. Сравнения можно почленно складывать. <tex> a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text{ }m)</tex>
** Представляем сравнения, как в пункте "а" и складываем.
*3. Сравнения можно почленно перемножать. <tex> a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)</tex>
** Представляем сравнения, как в пункте "а", перемножаем, получим <tex> a_1a_2a_3 = b_1b_2b_3+mN</tex>, где N{{---}}целое.
*4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
** Действительно, из <tex>a \equiv b(mod \text{ } m)</tex>, <tex> a = a_1d, b = b_1d, (d,m)=1</tex> следует, что <tex> a-b = (a_1 - b_1)d \vdots m </tex>, поэтому <tex> a_1 \equiv b_1(mod \text{ } m)</tex>.
*5. Обе части сравнения можно умножить на одно и тоже число.
*6. Обе части сравнения и модуль можно разделить на их общий делитель.
