мы говорим, что два числа
a и
b равны (сравнимы) по модулю m, что обозначается как
a ≡
b (mod
m) где и
a, и
b отличаются на число, кратное
m. По сути, это значит, что
a≡b(modm), еслиa=b+qmпри целом значенииq.
Самая интересное в таких сравнениях по модулю – что ведут они себя абсолютно так же, как и обычные уравнения. Вот почему мы можем пользоваться здесь модульной (модулярной) арифметикой, то есть арифметическими действиями над абсолютными значениями чисел и спокойно их складывать, вычитать и умножать. Например, если a ≡ b (mod m), а с – это любое целое число, верно будет, что
Итак, разнообразые сравнения можно складывать, вычитать и умножать. Например, если a ≡ b (mod m), а c ≡ d (mod m), значит,
Чуть более конкретно: так как 14 ≡ 2, а 17 ≡ 5 (mod 12), 14 × 17 ≡ 2 × 5 (mod 12), и это подтверждает, что 238 = 10 + (12 × 19). Следствием этого правила является то, что мы можем возводить сравнения по модулю в различные степени. Поэтому, если a ≡ b (mod m), действует следующее правило степени:
a²≡b² a³≡b³ ··· a>n≡b>n(modm)
при положительном целом значении n.
Отступление
Почему работает модульная арифметика? Например, если a ≡ b (mod m), а c ≡ d (mod m), значит, a = b + pm, а c = d + qm для целых значений p и q. Следовательно, a + c = (b + d) + (p + q)m, а a + c ≡ b + d (mod m). Далее, применив правило FOIL, получаем
ac =(b + pm)(d + qm)= bd +(bq + pd + pqm)m
Значит, ac и bd отличаются друг от друга на число, кратное m, что приводит нас к ac ≡ bd (mod m). Умножение соответствия a ≡ b (mod m) на само себя дает a² ≡ b² (mod m); повторение этого процесса опять-таки приводит нас к правилу возведения в степень.
То же правило возведения в степень делает число 9 таким особенным в десятеричной системе. Так как
то, согласно правилу возведения в степень, 10n ≡ 1n = 1 (mod 9) для любого значения n. Значит, например, число 3456 соответствует
3456 = 3(1000) + 4(100) + 5(10) + 6 ≡ 3(1) + 4(1) + 5(1) + 6 = 3 + 4 + 5 + 6 (mod 9)
А если 10 ≡ 1 (mod 3), становится понятно, почему мы можем простым сложением цифр определить, является ли число кратным 3 (или каким будет остаток при делении его на 3). Если бы мы проводили вычисления в другой системе – скажем, основанной на 16 (она называется шестнадцатеричной и используется в электротехнике и программировании), – то, исходя из 16 ≡ 1 (mod 15), мы могли бы простым сложением цифр определить, является ли число кратным 15 (или 3, или 5), или найти остаток при делении его на 15.
