9 × 9 = 9 × 9 × 9 = 9 × 9 × 9 × 9 = 94 = 9 (modulo 12).

3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3.

Малая теорема Ферма

Ниже приведено объяснение малой теоремы Ферма. Теорема утверждает, что в случае циферблата с простым числом 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. И эти два ответа равны на нашем часовом калькуляторе: