Мир математики. т.3. Простые числа. Долгая дорога к бесконечности
Шрифт:
Такой подход, уже известный математикам того времени, позволил Гауссу разработать новый вычислительный инструмент, который оказался очень полезным при определении некоторых свойств простых чисел.
* * *
МАГИЧЕСКИЕ КВАДРАТЫ
Сложение по правилу магических сумм обычно осуществлялось в магических квадратах. Это квадратные таблицы, заполненные числами таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях одинакова. Во многих культурах встречаются магические квадраты. Они интересовали многих известных математиков: Штифеля, Ферма, Паскаля, Лейбница и даже Эйлера.
Магический квадрат с гравюры «Меланхолия 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
Но в выражении такого рода чего-то не хватает. Нам нужно знать, какой тип «часов» мы использовали. В данном случае на циферблате часов было всего пять цифр. Это записывается как mod 5, и окончательное выражение выглядит следующим образом:
17
Это выражение означает, что числа 17 и 2 эквивалентны по модулю 5. Как было
Модульная арифметика вместо равенств использует сравнения по модулю, поэтому вышеприведенное выражение читается так: «17 сравнимо с 2 по модулю 5». Чтобы выяснить, сравнимы ли два числа по модулю 5, нужно вычесть одно из другого и проверить, делится ли результат на 5. В нашем случае 17 — 2 = 15, а число 15 кратно 5.
82
Дав определение модуля (циферблата на часах Гаусса), мы можем говорить о группах, или классах по модулю. Предположим, у нас имеется циферблат с четырьмя числами, то есть мы работаем с модулем 4. Значит, у нас будет только четыре группы, или класса чисел, простейшие представители которых — 0, 1, 2 и 3. Это означает, что мы можем использовать число 2 вместо числа 382, так как 382 при делении на 4 дает в остатке 2. Таким образом, мы можем составить следующую таблицу сложения:
Например, 2 + 3 = 5, но на циферблате с четырьмя числами 5 эквивалентно 1, то есть 5
Эта таблица содержит любопытный факт: при перемножении двух неравных нулю чисел получается ноль (2 x 2 = 0). То же самое будет с числами 2 и 3 в таблице умножения по модулю 6, так как 2 x 3 = 6, что эквивалентно нулю, потому что 6
Здесь простые числа и играют свою роль. Конгруэнтность в некоторой степени изучается в средней школе, но лишь когда мы обращаемся к сложной модульной арифметике, все становится действительно интересным, а простые числа — незаменимыми.
«Часы Гаусса» оказались чрезвычайно мощным инструментом. Гаусс мог определить, например, не выполняя сложных расчетов, что деление 8514 на 7 дает в остатке 1, так как 8
Следовательно, умножить число 8 на само себя 514 раз — все равно что умножить его на единицу столько же раз. Другими словами,
8514
Гаусс заметил, что если циферблат его часов содержит простое количество чисел, р, то они будут повторяться каждые р раз, то есть они образуют повторяющиеся группы из р чисел. Тогда Гаусс переформулировал малую теорему Ферма в терминах модульной арифметики: