Применения линейных сравнений по модулю m.

Одно из многих применений — древний алгоритм проверки ошибок, который изучается в средней школе и известен под названием «отбрасывание девяток». Когда мы складываем десятичные числа в столбик, то если в некотором столбце сумма цифр превышает 9, мы приводим ее по модулю 10 и прибавляем 1 или 2, или 3 и т.д. к следующему столбцу. Если рассматривать сумму десятичных цифр всех чисел, то мы прибавляем к ней 1 или 2, или 3 и т.д. и вычитаем из нее 10 или 20, или 30 и т.д. Поэтому сумма цифр не изменяется по модулю 9. [Можно также заметить, что

Пример. Рассмотрим сложение двух чисел:

Мы видим, что сумма цифр числа 178 равняется сумма цифр числа 34 и сумма цифр числа 16 также равны 7.

Аналогичный алгоритм проверки ошибок применим и к умножению:

Произведение сумм цифр равно сумма цифр этого произведения равна точно так же сумма цифр произведения 7743 равна Причиной того, что произведение сумм цифр чисел равно по модулю 9 произведению самих чисел, является сравнение к 0. Единственным недостатком этого древнего алгоритма проверки ошибок является то, что он не всегда находит ошибку; 10% случайных ошибок остаются не обнаруженными.