То же правило возведения в степень делает число 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. Основывается он на том, что
Значит, 10n ≡ (–1)n (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, используется для проверки правильности штрихкодов, номеров кредитных и дебетовых карточек. Еще модульная арифметика играет важную роль в проектировании электронных схем и интернет-систем, обеспечивающих финансовую безопасность.
Календарные исчисления
Мой любимый математический фокус – определять день недели, в который родился человек, по году и дате. Допустим, ваша знакомая говорит вам, что родилась 2 мая 2002 года. Представьте себе ее удивление, когда вы почти мгновенно сообщите ей, что это был четверг. Куда более полезно с практической точки зрения умение определять день недели по любой предстоящей в этом или следующем году дате. В этом разделе я расскажу вам, как легко это делать с помощью математики.
Но перед тем как заняться непосредственно самим методом, давайте вспомним пару интересных фактов из истории календаря. Итак, Земле требуется примерно 365,25 дней, чтобы пройти путь вокруг Солнца. Поэтому обычный год у нас длится 365 дней, а четверти мы собираем вместе и раз в четыре года добавляем один «лишний» (его еще называют високосным) день – 29 февраля. Таким образом, за четырехлетний цикл у нас получается 4 × 365 + 1 = 1461 день, что очень близко к реальному, астрономическому, положению вещей. Именно эта идея и легла в основу юлианского календаря, составленного Юлием Цезарем более 2000 лет назад. Например, 2000 год – високосный. И каждый четвертый после него – тоже: 2004, 2008, 2012, 2016 и т. д., вплоть до последнего в этом столетии 2096. «А как же 2100? – спросите вы. – Он разве не будет високосным?» А вот и нет. Знаете почему?
Проблема в том, что более точная длительность астрономического года – 365,243 (что примерно на 11 минут меньше 365,25), поэтому високосных годов получается чересчур много. За четыре сотни оборотов вокруг Солнца человечество проживает 146 097 дней, а юлианский календарь насчитывает 400 × 365,25 = 146 100 дней (что на три дня больше). Эту проблему (как и проблемы, связанные с определением дня Пасхи) попытался решить в 1582 году папа римский Григорий XIII, представив свой вариант календаря, впоследствии названный григорианским. И именно по этой самой причине в этом самом году католики всего мира убрали из своего летоисчисления десять дней. Например, в Испании после юлианского четверга 4 октября 1582 года последовала григорианская пятница, ставшая 15 октября 1582 года. После введения григорианского календаря годы, числовые значения которых можно разделить без остатка на 100, но при этом нельзя разделить без остатка на 400, перестали быть високосными (что позволило убрать лишние три дня). Следовательно, 1600 год в григорианском календаре оставался високосным, а вот 1700-й, 1800-й и 1900-й этот статус потеряли. Точно так же 2000-й и 2400-й – високосные, а 2100-й, 2200-й и 2300-й – нет. Согласно этой системе, каждые четыре сотни лет мы имеем 100 – 3 = 97 високосных годов или (400 × 365) + 97 = 146 097 дней, что точно соответствует астрономической истине.
