Артур Бенджамин - Магия математики - Как найти x и зачем это нужно

Значит, ac и bd отличаются друг от друга на число, кратное m , что приводит нас к ac ≡ bd (mod m ). Умножение соответствия a ≡ b (mod m ) на само себя дает a ² ≡ b ² (mod m ); повторение этого процесса опять-таки приводит нас к правилу возведения в степень.

То же правило возведения в степень делает число 9 таким особенным в десятеричной системе. Так как

то, согласно правилу возведения в степень, 10n ≡ 1n = 1 (mod 9) для любого значения n . Значит, например, число 3456 соответствует

А если 10 ≡ 1 (mod 3), становится понятно, почему мы можем простым сложением цифр определить, является ли число кратным 3 (или каким будет остаток при делении его на 3). Если бы мы проводили вычисления в другой системе – скажем, основанной на 16 (она называется шестнадцатеричной и используется в электротехнике и программировании), – то, исходя из 16 ≡ 1 (mod 15), мы могли бы простым сложением цифр определить, является ли число кратным 15 (или 3, или 5), или найти остаток при делении его на 15.

Но вернемся к более привычной десятеричной системе. Есть простой способ определить, кратно ли определенное число 11. Основывается он на том, что

Значит, 10 n≡ (–1) n(mod 11). Следовательно, 10² ≡ 1 (mod 11), 10³ ≡ (–1) (mod 11) и т. д. Число 3456, например, соответствует

То есть 3456 делится на 11 с остатком 2. Общее правило звучит так: число является кратным 11 только при условии, что мы приходим к числу, кратному 11 (например, 0, ± 11, ± 22….), при поочередном вычитании и сложении цифр. Давайте попробуем разобраться, делится ли число 31 415 на 11 без остатка? Достаточно посчитать 3 – 1 + 4 – 1 + 5 = 10, чтобы понять, что не делится, но сумма цифр следующего за ним целого 31 416 будет равна 11, поэтому 31 416 кратно 11.

Расчеты по модулю 11, кстати, используются для работы с ISBN [4]. Допустим, у вас есть книжка с десятизначным ISBN (номер с таким количеством цифр присваивался большинству книг до 2007 года). Эти цифры обозначают страну, в которой была издана книга, издательство и название, все, кроме последней, десятой, которую еще называют контрольной , – она нужна для того, чтобы превращать нагромождение цифр в стройную систему. То есть если десятизначный номер выглядит как a - bcd - efghi - j , тогда j выбирается на том основании, чтобы соответствовать

Так, ISBN моей книжки «Секреты устного счета», изданной в 2006-м, – 0-307-33840-1, что соответствует

поскольку 154 = 11 × 14. В А что происходит, когда возникает необходимость в качестве контрольной цифры поставить 10? В этом случае вместо десятки ставят литеру X – она же римская десятка. Система ISBN хороша тем, что позволяет легко определить ошибку в случае, если одна из цифр введена неправильно. Например, если вы перепутали третью цифру, то общий результат окажется кратным 8: ± 8, ± 16… ± 80, а не 11 (вы ведь помните, что 11 у нас здесь – главное число?), что и укажет на ошибку. С помощью алгебры легко убедиться, что система способна обнаружить ошибку даже в том случае, если две цифры перепутаны местами. Предположим, мы перепутали цифры c и f . При этом порядок остальных цифр верен, то есть единственное, что делает верный результат неверным – это значения c и f . Старый результат основан на 8 c + 5 f , новый – на 8 f + 5 c . Их разность (8 f + 5 c ) – (8 c + 5 f ) = 3( f – c ), о которой мы знаем, что она не кратна 11. Следовательно, и новый результат не кратен 11.

В 2007 г. издатели перешли на тринадцатизначную систему ISBN, основанную уже на модуле 10 вместо 11. То есть номер abc - d - efg - hijkl - m правилен только в том случае, если он соответствует

Похожая система, основанная на модуле 10, используется для проверки правильности штрихкодов, номеров кредитных и дебетовых карточек. Еще модульная арифметика играет важную роль в проектировании электронных схем и интернет-систем, обеспечивающих финансовую безопасность.