Теперь мы можем сказать, что число 78 относится к группе 6, а число 93 — к группе 3. На языке современной математики эти группы называются «классами эквивалентности». Таким образом, можно говорить о «классе числа 3», «классе числа 5» и так далее.
Такой подход, уже известный математикам того времени, позволил Гауссу разработать новый вычислительный инструмент, который оказался очень полезным при определении некоторых свойств простых чисел.
* * *
МАГИЧЕСКИЕ КВАДРАТЫ
Сложение по правилу магических сумм обычно осуществлялось в магических квадратах. Это квадратные таблицы, заполненные числами таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях одинакова. Во многих культурах встречаются магические квадраты. Они интересовали многих известных математиков: Штифеля, Ферма, Паскаля, Лейбница и даже Эйлера. В настоящее время существуют алгоритмы для построения большинства магических квадратов.
Магический квадрат с гравюры «Меланхолия I» художника эпохи Возрождения, Альбрехта Дюрера.
* * *
Часы Гаусса
Циферблат часов содержит 12 чисел, расположенных по кругу. После числа 12 должно идти число 13, но мы на самом деле возвращаемся к единице и начинаем новый отсчет. Эта система практически не отличается от правила магических сумм, только вместо первых девяти чисел здесь используются первые двенадцать. Мы могли бы составить таблицу, аналогичную предыдущей, только с двенадцатью столбцами вместо девяти. Напишем первые две строки такой таблицы:
Это именно то, что мы делаем каждый раз, когда смотрим на часы с цифровым циферблатом. Чтобы определить время после полудня, мы считаем до 12, а затем начинаем сначала с единицы. Например, когда мы видим на часах цифры 17:00, мы знаем, что это означает «5 часов дня», так как число 17 согласно нашей таблице находится в том же «классе», что и 5. Так у Гаусса появилась идея использовать различные часы или, точнее, разные циферблаты часов. Например, для часов, на циферблате которых нанесены лишь первые пять чисел, можно составить такую таблицу:
Согласно нашему предыдущему критерию, можно сказать, что число 17 находится в группе числа 2, или, точнее, 17 принадлежит классу числа 2.
Определить класс числа совсем нетрудно. Возьмем, например, число 18: сделаем три полных оборота, получим число 15, а затем начнем отсчет сначала и получим число 3, что означает, что число 18 относится к классу числа 3. Это то же самое, что разделить 18 на 5 и получить остаток 3. Такой способ очень полезен для больших чисел. Чтобы узнать, к какому классу принадлежит, например, число 40248, мы делим его на 5 и получаем частное 8049 и остаток 3. Значит, 40248 относится к классу числа 3. Так как числа, кратные пяти, дают в остатке ноль, мы используем 0 для обозначения класса числа 5 и перепишем нашу таблицу следующим образом:
Можно сказать, что в этом смысле число 17 такое же, что и число 2, но знак равенства 17 = 2 сбивал бы нас с толку, поэтому этот факт обычно записывается как 17 2.
Но в выражении такого рода чего-то не хватает. Нам нужно знать, какой тип «часов» мы использовали. В данном случае на циферблате часов было всего пять цифр. Это записывается как mod 5, и окончательное выражение выглядит следующим образом:
17 2 (mod 5).
Это выражение означает, что числа 17 и 2 эквивалентны по модулю 5. Как было принято в то время, Гаусс писал научные работы на латинском языке, поэтому он выбрал слово «по модулю» (modulo, творительный падеж слова modulus, означающего «абсолютное значение»). В результате родилась так называемая модульная арифметика, которая и сегодня является одним из самых мощных инструментов в теории чисел.
Сравнения по модулю
Модульная арифметика вместо равенств использует сравнения по модулю, поэтому вышеприведенное выражение читается так: «17 сравнимо с 2 по модулю 5». Чтобы выяснить, сравнимы ли два числа по модулю 5, нужно вычесть одно из другого и проверить, делится ли результат на 5. В нашем случае 17 — 2 = 15, а число 15 кратно 5.
82 58 (mod 4), потому что 82–58 = 24, которое кратно 4.
Дав определение модуля (циферблата на часах Гаусса), мы можем говорить о группах, или классах по модулю. Предположим, у нас имеется циферблат с четырьмя числами, то есть мы работаем с модулем 4. Значит, у нас будет только четыре группы, или класса чисел, простейшие представители которых — 0, 1, 2 и 3. Это означает, что мы можем использовать число 2 вместо числа 382, так как 382 при делении на 4 дает в остатке 2. Таким образом, мы можем составить следующую таблицу сложения:
Например, 2 + 3 = 5, но на циферблате с четырьмя числами 5 эквивалентно 1, то есть 5 1 (mod 4). Аналогично составим таблицу умножения:
Эта таблица содержит любопытный факт: при перемножении двух неравных нулю чисел получается ноль (2 x 2 = 0). То же самое будет с числами 2 и 3 в таблице умножения по модулю 6, так как 2 x 3 = 6, что эквивалентно нулю, потому что 6 0 (mod 6). Такого не произойдет, если модуль является простым числом, потому что простое число нельзя разложить на произведение множителей.
Здесь простые числа и играют свою роль. Конгруэнтность в некоторой степени изучается в средней школе, но лишь когда мы обращаемся к сложной модульной арифметике, все становится действительно интересным, а простые числа — незаменимыми.
«Часы Гаусса» оказались чрезвычайно мощным инструментом. Гаусс мог определить, например, не выполняя сложных расчетов, что деление 8514 на 7 дает в остатке 1, так как 8 1 (mod 7), то есть 8 при делении на 7 дает в остатке 1, а таблица умножения показывает, что умножение 8 на 8 эквивалентно умножению 8 на 1: 8 х 8 = 64, которое при делении на 7 дает в остатке 1.
Следовательно, умножить число 8 на само себя 514 раз — все равно что умножить его на единицу столько же раз. Другими словами,
8514 1 (mod 7).
Гаусс заметил, что если циферблат его часов содержит простое количество чисел, р, то они будут повторяться каждые р раз, то есть они образуют повторяющиеся группы из р чисел. Тогда Гаусс переформулировал малую теорему Ферма в терминах модульной арифметики:
«Если р — простое число, то для любого натурального числа а ар а (mod р)».
Или, что то же самое, (ар — а) кратно р. Например, З5 —3 = 240, и 240 кратно 5. В терминах «часов Гаусса» теорему можно интерпретировать следующим образом. Предположим, мы хотим знать, является ли р простым числом. Построим часы с циферблатом, содержащим р делений. Возьмем любое число на циферблате, возведем его в степень р и проверим, будет ли стрелка указывать на то же число. Если нет, то мы можем быть уверены, что р не является простым числом. Например, пусть р равно 6. Построим часы с циферблатом, содержащим 6 делений. Возьмем одно из чисел, например, 4. Запишем 46 = 4096, что при делении на 6 дает в остатке 4.
Иначе говоря, стрелки часов делают круг за кругом, пока не остановятся на цифре 4. Мы знаем, что по малой теореме Ферма число 6 не является простым. Возьмем теперь простое число, например, 7, и посмотрим, что произойдет, когда мы возведем некоторое число в седьмую степень. Укажут ли стрелки часов на это число? Однако мы должны иметь в виду, что теорема дает необходимое, но не достаточное условие.
Это означает, что если при проверке числа а стрелки укажут на это число а, существует вероятность, что число р окажется простым. Но одной такой проверки недостаточно. Чем больше проверок мы сделаем, тем больше шанс, что число р является простым, но мы не можем утверждать это наверняка. Как мы увидим в седьмой главе, это один из способов, широко используемый современными компьютерами для определения простоты больших чисел.
Мнимые числа
Услышав выражение «мнимые числа», человек, далекий от математики, может подумать, что это еще одна причуда математиков, и будет недалек от истины. Такое мнение разделяли и многие специалисты в области математики, когда им встречались числа настолько экзотические, что к ним относились почти как к призракам.
Но эти призраки настойчиво появлялись при решении уравнений, и вскоре их стало невозможно игнорировать. Их начали использовать при расчетах, и в конце концов они были приняты в качестве решений уравнений и приобрели собственный статус, став одним из фундаментальных понятий в математике и важнейшей темой многих учебников. Было бы неправильно полагать, что они появляются лишь в мире чистой математики. На самом деле мнимые числа являются основным инструментом современной физики и самым различным образом применяются на практике.
