9 × 9 = 9 × 9 × 9 = 9 × 9 × 9 × 9 = 94 = 9 (modulo 12).
Ответ на часовом калькуляторе можно получить, сделав вычисления на обычном калькуляторе и затем взяв остаток от деления на число часовых делений. Но сила часового калькулятора состоит в том, что часто вам вовсе не требуется совершать вычисление на обычном калькуляторе. Вы можете найти, чему равно 799, на 12-часовом калькуляторе? Подсказка: сначала вычислите 7 × 7, а потом снова умножьте результат на 7. Вы видите закономерность?
Ферма сделал фундаментальное открытие о вычислениях на калькуляторе, у которого имеется простое число часовых делений. Обозначим его, к примеру, p. Ферма обнаружил, что если вы возьмете какое-то число с циферблата и возведете его в степень p, то придете к тому же числу, с которого стартовали. Это утверждение сейчас называется малой теоремой Ферма, в отличие от его знаменитой Великой теоремы.
В таблице 4.13 приведены некоторые вычисления на калькуляторах с простым и составным числом часов.
Таблица 4.13
Поскольку число 5 – простое, при возведении 2 в пятую степень на 5-часовом калькуляторе получится снова 2. Итак, 25 =2 (modulo 5). Магия будет гарантированно работать, если на калькуляторе простое число часов. Она может не удаться, если вы возьмете калькулятор с составным числом часов. Например, 6 – составное число, и на 6-часовом калькуляторе 26оказывается равным не 2, а 4.
По мере того как стрелка перемещается по часам, начинает проступать закономерность. Поскольку после p – 1 шагов мы гарантированно возвращаемся в то место, с которого стартовали, последовательность начинает повторяться через p – 1 шаг. Порою последовательность повторяется несколько раз на протяжении p – 1 шагов. Вот что мы увидим на циферблате с 13 часами, когда будем возводить 3 в последовательные степени 3¹, 3² и так далее вплоть до 3¹³:
3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3.
Стрелка не посещает все деления на часах, тем не менее по-прежнему имеется повторяющаяся закономерность, которая приводит стрелку назад к 3 часам после перемножения тринадцати троек.
Мы уже сталкивались с похожей математикой в главе 3, когда рассматривали жульнический прием совершенных тасовок в покере. Там мы варьировали число карт в колоде и задавались вопросом, сколько совершенных тасовок необходимо сделать, чтобы карты возвратились к первоначальному расположению. В колоде с 2N картами порою необходимо выполнить все 2N – 2 совершенных тасовок, но бывает, их требуется сделать значительно меньше. Если в колоде 52 карты, то после всего лишь 8 совершенных тасовок они вернутся к исходному расположению. Но колода с 54 картами требует 52 совершенных тасовок.
Ферма никогда не излагал в полной мере свои рассуждения, поэтому он оставил в виде задания для будущих поколений математиков объяснение своего открытия, что магия всегда срабатывает для часов с простым числом делений. В конечном счете доказательство было найдено Леонардом Эйлером.
Малая теорема Ферма
Ниже приведено объяснение малой теоремы Ферма. Теорема утверждает, что в случае циферблата с простым числом p часовых делений
Ap = A (modulo p).
Для понимания доказательства нужны усилия, но не специальные знания: чтобы вы могли проследить его, требуется лишь сосредоточенность.
В качестве первого шага рассмотрим простой случай. Если A = 0, то теорема верна, потому что сколько бы раз мы ни умножили 0 на себя, все равно получится 0. Поэтому давайте предположим, что А не равно нулю. Мы намереваемся показать, что произведение p – 1 множителя А равно 1. Этого достаточно для доказательства теоремы, поскольку умножение 1 на А возвратит нас к А.
Теперь давайте составим список всех часов на циферблате за исключением 0. В этом списке p – 1 элемент:
1, 2, …, p – 1.
Теперь умножим каждое число в этом списке на А и получим
А × 1, А × 2, …, А × (p – 1) (modulo p).
Позвольте мне показать, что часы в этом списке будут теми же, что и в первоначальном списке 1, 2, …, p – 1, хотя они будут расположены в другом порядке. Если бы это было не так, то либо одно из произведений равнялось бы 0, либо какие-то два произведения были равны друг другу. Не может произойти что-либо другое, поскольку на циферблате имеется лишь p часов.
Предположим, что А × n и А × m дают один и тот же ответ на нашем p-часовом циферблате, где n и m лежат между 1 и p – 1 (я покажу, почему это означает, что n = m). Итак, А × n – А × m = А × (n – m) равно нулю на часовом калькуляторе, то есть А × (n – m) на обычном калькуляторе делится на p.
Ключевым в следующем шаге доказательства будет использование того факта, что p – простое число. Подобно химической молекуле, число А × (n – m) построено из произведения атомов (простых чисел), составляющих А, и простых чисел, составляющих n – m. Но число p – простое, атом арифметики, и его нельзя расщепить далее. Поскольку А × (n – m) делится на p, это число должно быть одним из атомов, использованных при построении А × (n – m), ведь каждое число однозначно разлагается на простые множители. Но А не делится на p без остатка, поэтому p должно входить в список атомов, использованных при построении n – m. Другими словами, n – m делится на p. Но что это означает? Это означает, что n и m соответствуют одному и тому же времени на нашем p-часовом циферблате. Вы можете использовать схожую аргументацию, чтобы показать, что А × n не может быть нулем часов, если ни А, ни n не равны нулю часов.
Заметьте, что крайне важно то, что на циферблате простое число часов. Мы уже видели, что 4 × 9 равняется нулю на 12-часовом калькуляторе, хотя ни 4, ни 9 не равно нулю.
Теперь у нас есть два списка – 1, 2, …, p – 1 и А × 1, А × 2, …, А × (p – 1), – составленные из одних и тех же чисел, хотя и расположенных в разном порядке. Теперь мы можем воспользоваться эффектным трюком, который, вероятно, открыл сам Ферма. Если мы перемножим все числа в каждом из списков, то получим один и тот же ответ, потому что порядок перемножения не имеет значения. Первый список даст нам 1 × 2 × … × (p – 1), что мы можем записать как (p – 1)!. Второй список приводит к p – 1 множителю А и опять-таки произведению чисел от 1 до p – 1. После небольшой перестановки мы можем переписать это как (p – 1)!× Аp – 1. И эти два ответа равны на нашем часовом калькуляторе:
