Магия 10, 11, 12 и модульной арифметики

Многое из того, что мы узнали о девятке, справедливо и в отношении других чисел. Вычисляя вычет по модулю 9, мы, по сути, заменяем числа тем, что осталось от их деления на 9. Не думаю, что для вас это большая новость. Каждый из нас делает это практически каждый день – с тех самых пор, когда мы научились называть время. Допустим, часы показывают ровно 8 (утра или вечера – неважно). Сколько они будут показывать через 3 часа? А через 15 часов? А через 27? А сколько они показывали 9 часов назад? Первые числа, которые возникают в сознании – 11, 23, 35, –1, но стоит нам вспомнить, что речь идет о часах, мы понимаем, что ответ на все эти вопросы будет один и тот же – 11 часов, ведь все заданные промежутки должны считаться от 12. Математики используют для этого такого вот вида запись:

Обобщая, мы можем сказать, что a ? b (mod 12), где и a, и b отличаются на число, кратное 12. Соответственно, a ? b (mod 12), если и a, и b при делении на 12 имеют один и тот же остаток. Иными словами, для любого целого значения m мы говорим, что два числа a и b равны (сравнимы) по модулю m, что обозначается как a ? b (mod m) где и a, и b отличаются на число, кратное m. По сути, это значит, что

a ? b (mod m), если a = b + qm при целом значении q.

Самая интересное в таких сравнениях по модулю – что ведут они себя абсолютно так же, как и обычные уравнения. Вот почему мы можем пользоваться здесь модульной (модулярной) арифметикой, то есть арифметическими действиями над абсолютными значениями чисел и спокойно их складывать, вычитать и умножать. Например, если a ? b (mod m), а с – это любое целое число, верно будет, что

a + c ? b + c, а ac ? bc (mod m)

Итак, разнообразые сравнения можно складывать, вычитать и умножать. Например, если a ? b (mod m), а c ? d (mod m), значит,

a + c ? b + d, а ac ? bd (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ⁿ ? bⁿ (mod m)

при положительном целом значении 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 таким особенным в десятеричной системе. Так как

10 ? 1 (mod 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.

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

10 ? –1 (mod 11)

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

3456 = 3(1000) + 4(100) + 5(10) + 6 ? –3 + 4 – 5 + 6 = 2 (mod 11)

То есть 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 выбирается на том основании, чтобы соответствовать

10a + 9b + 8c + 7d + 6e + 5f + 4g + 3h + 2i + j ? 0 (mod 11)

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

10(0) + 9(3) + 8(0) + 7(7) + 6(3) + 5(3) + 4(8) + 3(4) + 2(0) + 1 = 154 ? 0 (mod 11)

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

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

a + 3b + c + 3d + e + 3f + g + 3h + i + 3j + k + 3l + m ? 0 (mod 10)

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