Артур Бенджамин - Магия математики: Как найти x и зачем это нужно
Самая интересное в таких сравнениях по модулю – что ведут они себя абсолютно так же, как и обычные уравнения. Вот почему мы можем пользоваться здесь модульной (модулярной) арифметикой, то есть арифметическими действиями над абсолютными значениями чисел и спокойно их складывать, вычитать и умножать. Например, если 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³ ··· an ≡ bn (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)Значит, 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? – спросите вы. – Он разве не будет високосным?» А вот и нет. Знаете почему?
