Тайны чисел: Математическая одиссея

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

Ниже приведено объяснение малой теоремы Ферма. Теорема утверждает, что в случае циферблата с простым числом p часовых делений

A^p = 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. И эти два ответа равны на нашем часовом калькуляторе:

(p – 1)! = (p – 1)! × А^p – 1 (modulo p).

Из этого следует, что (p –  1)! × (1 – А^p – 1) делится на p, и мы можем использовать тот же трюк, что и ранее. Никакое из чисел 1, 2, …, p – 1 не делится на p, значит, (p –  1)! не может делиться на p. Единственная возможность состоит в том, что 1 – А^p – 1 делится на p. А это приводит к тому, что вычисление А^p – 1 на часовом калькуляторе всегда будет давать ответ 1 – предложением объяснить данный результат Ферма и раззадорил математиков.

В этой аргументации есть несколько интересных ингредиентов. Разумеется, немаловажно то обстоятельство, что если A × B делится без остатка на простое число p, то либо А, либо B должно также делиться на данное простое число. Это следует из специального свойства простых чисел. Но мне представляется красивым взгляд на список 1, 2, …, p – 1 с двух различных перспектив. Для меня это образец умения рассматривать задачу с разных сторон.