Текст книги "Магия математики: Как найти x и зачем это нужно"

Магия 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]4
  ISBN – Международный стандартный книжный номер (англ. International Standard Book Number) – уникальный номер книжного издания, необходимый для распространения книги в торговых сетях и автоматизации работы с изданием. – Прим. пер.


[Закрыть]. Допустим, у вас есть книжка с десятизначным 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 дней, что точно соответствует астрономической истине.

Некоторые страны – в основном, некатолические – далеко не сразу приняли григорианский календарь. Англия вместе со своими колониями, например, перешла на него только в 1752 году, когда за средой 2 сентября сразу же последовал четверг 14 сентября (обратите внимание, что они «потеряли» 11 дней, а не десять, потому что пропустили 1700 год, который в юлианском календаре был високосным, а в григорианском – обычным). Всемирное же распространение григорианский календарь получил только в 1920 году. Представьте, какой головной болью это стало для историков. Мой любимый исторический парадокс – смерти Уильяма Шекспира и Мигеля де Сервантеса, которые по справочникам случились в один день, 23 апреля 1616 года, а на деле – с разницей в десять дней. Все это как раз из-за того, что к моменту смерти Сервантеса Испания уже пользовалась григорианским календарем, а Англия – все еще юлианским. То есть григорианское 23 апреля 1616 года в Испании было юлианским 13 апреля 1616 года в Англии, где жил (и прожил еще десять дней) Шекспир.

Формула определения дня недели по любой дате григорианского календаря выглядит так:

День недели ≡ код месяца + дата + код года (mod 7)

Давайте разберемся, что здесь к чему. Все это имеет смысл, если формула использует модульную арифметику по модулю 7 (поскольку в неделе 7 дней). Например, если нас интересует дата через 72 дня, день недели будет на два впереди от сегодняшнего, потому что 72 ≡ 2 (mod 7). А вот дата через 28 дней придется на тот же день недели, потому что 28 делится на 7 без остатка.

Начнем, пожалуй, с кодов дней недели – их легче всего запомнить:

По большому счету, здесь и запоминать-то ничего не надо: все точно соответствует привычной нам системе (ну, кроме воскресенья, которое, кроме 7, может быть и 0)[5]5
  На самом деле автор приводит в таблице мнемонические упражнения, что вызвано американской традицией считать начало новой недели с воскресенья – это вызывает «сдвиг» кодов по отношению к порядку дней недели и, возможно, необходимость действительно эти коды запоминать. Так или иначе, переводчик взял на себя смелость исключить в своей редакции конкретно эти мнемонические упражнения во избежание возможной путаницы и переизбытка информации, которая и без того хорошо знакома любому русскому читателю. – Прим. пер.


[Закрыть].

Отступление[6]6
  В Древней Руси «блок» из семи дней назывался а «седмицей» (родство со словом «семь», думаю, очевидно). «Неделей» же называлось современное нам воскресенье – исключительно потому, что в этот день принято было ничего НЕ ДЕЛать. Название «воскресенье», закрепившееся в XVII веке, восходит к празднику Пасхи (воскресению Иисуса Христа).
  К слову сказать, «неделя» считалась первым (а не последним, как сейчас) днем седмицы, поэтому второй день назывался «понедельник» – то есть следующий после «недельника». «Вторник» – второй день после праздника, «среда» – «середина» седмицы, «четверг» и «пятница» – соответственно, четвертый и пятый дни. «Суббота» же уходит своими корнями в еврейские традиции, к слову «шаббат», которое означает «покой», «отдых». – Прим. пер.


[Закрыть]

Откуда пошли английские названия дней недели? Корнями они уходят в традиции Вавилонского царства, где были связаны с именами Солнца, Луны и пяти других ближайших к Земле небесных тел. От Солнца (англ. Sun) произошло воскресенье (англ. Sun-day), от Луны (англ. Moon) – понедельник (англ. Mon-day), от Сатурна – суббота (англ. Satur-day). Остальные названия легче найти во французском или, скажем, испанском языках. Так, Марс (лат. Mars) превратился во французское Mardi и испанское Martes (вторник), Меркурий (лат. Mercurius) – в Mercredi и Miércoles (среда), Юпитер (лат. Jupiter) – в Jeudi и Jueves (четверг), Венера (лат. Venus) – в Vendredi и Viernes (пятница). Обратите внимание, что и Марс, и Меркурий, и Юпитер, и Венера – не только названия планет, но и имена древнеримских богов. Английский же язык благодаря своему германскому происхождению перенял названия оставшихся четырех дней недели из скандинавской мифологии, в которой бога войны Марса звали Тиу (англ. Tiw), отца богов Юпитера – Тором (англ. Thor), его сына Меркурия – Одином (англ. Woden), а богиню любви и плодородия Венеру – Фрейей (англ. Freya). Так и появились «день Тиу» – вторник (англ. Tues-day), «день Одина» – среда (англ. Wednes-day), «день Тора» – четверг (англ. Thurs-day) и «день Фрейи» – пятница (англ. Fri-day).

А вот с кодами месяцев мороки чуть больше, поэтому здесь я приведу «запоминалки» – подсказки, основанные на ассоциации.

Откуда берутся эти цифры, я объясню чуть позже – сначала разберемся с вычислениями. Единственный код года, который вам пока нужно знать, – 0 для 2000 года. Давайте попытаемся посчитать, на какой день недели пришлось в этом году 19 марта (мой день рождения, кстати). Код марта у нас – 2, код 2000 года – 0, подставляем их в нашу формулу и получаем

День недели = 2 + 19 + 0 = 21 ≡ 0 (mod 7)

Значит, 19 мая 2000 года было воскресеньем.

Отступление

Быстренько объясним, откуда берутся коды месяцев. Обратите внимание, что в невисокосные годы коды февраля и марта совпадают. Объясняется это тем, что в феврале 28 дней, а значит, 1 марта наступает через 28 дней после 1 февраля – то есть оба эти месяца начинаются в один и тот же день недели. А теперь смотрите: 1 марта 2000 года было средой. Поэтому, если мы присвоим 2000 году код 0, а понедельнику – код 1, марту просто некуда деваться, как получить код 2. Поэтому в невисокосный год кодом февраля тоже должна быть двойка. А раз в марте у нас 31 день, что ровно на 3 больше февральских 28, календарь апреля сдвигается по неделе на 3 дня вперед, то есть код получается 2 + 3 = 5. Дальше мы добавляем апрельские 28 + 2 к коду 5 и видим, что код мая должен быть 5 + 2 = 7, которые мы можем заменить на 0, раз уж наш модуль – 7. Точно так же мы можем определить коды и всех остальных месяцев.

С другой стороны, в феврале високосного года (а 2000 год был високосным) 29 дней, поэтому календарь марта убегает только на один день вперед, а код такого февраля будет 2 – 1 = 1. В январе 31 день, поэтому его код в невисокосном году должен быть на три единицы меньше кода февраля: 2 – 3 = –1 ≡ 6 (mod 7). В високосный же год получается на единицу меньше: 1 – 3 = –2 ≡ 5 (mod 7).

Что происходит с вашим днем рождения от года к году? Если забыть про високосные годы, между двумя днями рождения проходит 365 дней, то есть каждый раз эта дата смещается на один день вверх по неделе, потому что 365 ≡ 1 (mod 7), а 365 = 52 × 7 + 1. Но когда между ними «вклинивается» 29 февраля, если вы, разумеется, не родились именно 29 февраля, смещение составит не один день, а два. Соответственно, к коду года в нашей формуле мы просто добавляем 1. Или 2, когда дело доходит до високосного года. Вот коды годов с 2000-го по 2031-й. Не переживайте. Их вам запоминать не придется.

Обратите внимание, что мы идем просто по порядку – 0, 1, 2, 3 и т. д., – перескакивая через единицу для високосного года. Так происходит в случае с 2004-м, кодом которого вместо 4 будет 5, 2005-й тогда получает код 6, а 2007-й должен бы получить 7, но, так как мы с вами работаем по модулю 7, возвращаемся обратно к 0, Поэтому код 2007-го – 1, а 2008-го (високосного) – 3.

И так далее. С помощью этой таблицы мы легко определим, что в 2025 году (это ближайший год, числовое обозначение которого является квадратом числа), день числа Пи (14 марта) придется на

День недели = 2 + 14 + 3 = 19 ≡ 5 (mod 7) = Пятница

А как насчет 1 января 2008 года? Не забудьте, что год этот – високосный, а значит, код января будет 5, а не 6. Следовательно:

День недели = 5 + 1 + 3 = 9 ≡ 2 (mod 7) = Вторник

Посмотрите еще раз на таблицу вдоль ее рядов, и увидите, что каждый раз, когда проходит 8 лет, код года повышается на 3 (по модулю 7). Например, годы в первом ряду имеют коды 0, 3, 6, 2 (двойка по модулю 7 – это та же девятка). Происходит это потому, что за период в 8 лет нам обязательно попадается два високосных года, поэтому даты смещаются на 8 + 2 = 10 ≡ 3 (mod 7).

А вот кое-что еще более интересное. С 1901 по 2099 год через каждые 28 лет календарь повторяется один в один. Знаете, почему? Из 28 лет 7 – всегда високосные, поэтому календарь смещается на 28 + 7 = 35 дней, а 35 – число, кратное 7, что и обеспечивает повторяемость дней недели (закономерность эта нарушится, если мы опустимся ниже 1900 года или поднимемся выше 2100-го, ведь в григорианском календаре они не високосные). Поэтому, просто складывая или вычитая числа, кратные 28, вы можете превратить любой год из промежутка с 1901-го по 2099-го в соответствующий ему из промежутка с 2000-го по 2027-й. Например, 1983-й имеет тот же код, что и 1983 + 28 = 2011, а 2061-й – тот же, что и 2061 – 56 = 2005.

То есть какую бы практическую задачу вы ни решали, вы можете превратить нужный вам год в один из тех, что составляют нашу таблицу, и таким нехитрым способом узнать его код. Почему, например, кодом 2017-го будет 0? Да потому что с 2000 года (имеющего код 0), календарь смещается по неделе 17 раз плюс дополнительно 4 раза за каждый високосный год – 2004-й, 2008-й, 2012-й и 2016-й. Значит, код 2017-го будет 17 + 4 = 21 ≡ 0 (mod 7). А что насчет 2020-го? Здесь у нас будет уже пять високосных годов (ведь сам 2020-й – високосный), поэтому календарь смещается 20 + 5 = 25 раз, а так как 25 ≡ 4 (mod 7), кодом 2020 года будет 4. Вот как будет выглядеть общая схема определения годовых кодов в промежутке с 2000-го по 2027-й.

Шаг 1: Возьмите две последние цифры года (в примере с 2022 годом этими цифрами будут 22).

Шаг 2: Разделите это число на 4. В результате нас интересует только целое, остаток можно проигнорировать (в нашем примере – 22 ÷ 4 = 5 с остатком 2).

Шаг 3: Сложите числа из первого и второго шагов (в нашем примере – 22 + 5 = 27).

Шаг 4: Возьмите ближайшее число, кратное 7, которое при этом будет меньше суммы, полученной после третьего шага (это может быть 0, 7, 14, 21 или 28). Вычтите его из этой суммы и узнаете код года (другими словами, сократите число из третьего шага по модулю 7: так как 27 – 21 = 6, кодом 2022 года будет 6).

Обратите внимание, что шаги с 1 по 4 работают для любого года в промежутке с 2000-го по 2099-й; можно значительно упростить себе задачу устного счета, просто вычтя на начальном этапе число, кратное 28, и получив таким образом год в промежутке с 2000-го по 2027-й. 2040 год, например, можно «упростить» до 2012, и шаги с 1-го по 4-й превращаются в элементарное 12 + 3 – 14 = 1. К тому же результату можно прийти, работая непосредственно с 2040: 40 + 10 – 49 = 1.

Алгоритм этот можно использовать не только для двухтысячных годов. Коды месяцев останутся такими же, а вот с кодами годов нужно будет сделать одну небольшую поправку. Код 1900 года будет равен 1. Следовательно, код каждого года в промежутке с 1900-го по 1999-й будет на одну единицу больше, чем их «собратья» в промежутке с 2000-го по 2099-й. То есть если код 2040-го – 1, значит, кодом 1940-го будет 2; а кодом 1922-го, например, будет 7 (ну, или 0), потому что 2022 год обозначается кодом 6. Код 1800 года – 3, 1700-го – 5, 1600-го – 0 (на самом деле на полный цикл у календаря уходит 400 лет, потому что именно четырехсотлетний период имеет 100 – 3 = 97 високосных годов, то есть ровно через 400 лет, день в день, календарь сместится на 400 + 97 = 497 дней, что даст нам абсолютно тот же день недели и то же число, ведь 497 кратно 7).

Хотите узнать, каким днем недели было 4 июля 1776 года? Сначала найдем код 2076 года, для чего вычтем 56 из 2076, а потом посчитаем код 2020-го: 20 + 5 – 21 = 4. Следовательно, код 1776 года будет 4 + 5 = 9 ≡ 2 (mod 7). Таким образом, получается, что по григорианскому календарю 4 июля 1776 года пришлось на

День недели = 5 + 4 + 2 = 11 ≡ 4 (mod 7) = Четверг

А раз так, может быть, те, кто подписывал Декларацию независимости, просто хотели успеть завершить все перед выходными?

Отступление

Под конец главы давайте я расскажу вам о еще одном волшебном свойстве числа 9. Загадайте любое число, в котором ни одна цифра не повторяется, при этом идут они от меньшего к большему. Это может быть, например, 12 345, 2358, 369 или 135 789. Умножьте это число на 9 и сложите между собой цифры. В том, что результат будет кратен 9, для нас ничего нового нет – удивительным будет то, что цифры в своей сумме дадут ровно 9. Например,

9 × 12 345 = 111 105

9 × 2358 = 21 222

9 × 369 = 3321

Фокус сработает, даже если цифры будут повторяться – главное, чтобы они шли от меньшего к большему и чтобы разряд единиц не равнялся разряду десятков. Вот, смотрите:

9 × 12 223 = 110 007

9 × 33 344 44 9 =300 100 041

Так в чем тут секрет? Давайте посмотрим, что происходит, когда мы умножаем на 9 число ABCDE, в котором A ≤ B ≤ C ≤ D < E. Так как умножать на 9 – все равно что умножать на 10 – 1, мы приходим к вычитанию

Если считать слева направо, то, с учетом того, что B ≥ A, C ≥ B, D ≥ C, а E > D, мы будем иметь дело с

а сумма цифр результата составит

A + (B – A) + (C – B) + (D – C) + (E – D – 1) + (10 – E) = 9

что и требовалось доказать.