Том 3. Простые числа. Долгая дорога к бесконечности - [23]

Согласно нашему предыдущему критерию, можно сказать, что число 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 раз — все равно что умножить его на единицу столько же раз. Другими словами,

8⁵¹⁴ 

1 (mod 7).

Гаусс заметил, что если циферблат его часов содержит простое количество чисел, р, то они будут повторяться каждые р раз, то есть они образуют повторяющиеся группы из р чисел. Тогда Гаусс переформулировал малую теорему Ферма в терминах модульной арифметики:

«Если р — простое число, то для любого натурального числа а а^р 

а (mod р)».

Или, что то же самое, (а^р — а) кратно р. Например, З⁵ —3 = 240, и 240 кратно 5. В терминах «часов Гаусса» теорему можно интерпретировать следующим образом. Предположим, мы хотим знать, является ли р простым числом. Построим часы с циферблатом, содержащим р делений. Возьмем любое число на циферблате, возведем его в степень р и проверим, будет ли стрелка указывать на то же число. Если нет, то мы можем быть уверены, что р не является простым числом. Например, пусть р равно 6. Построим часы с циферблатом, содержащим 6 делений. Возьмем одно из чисел, например, 4. Запишем 4⁶  = 4096, что при делении на 6 дает в остатке 4.

Иначе говоря, стрелки часов делают круг за кругом, пока не остановятся на цифре 4. Мы знаем, что по малой теореме Ферма число 6 не является простым. Возьмем теперь простое число, например, 7, и посмотрим, что произойдет, когда мы возведем некоторое число в седьмую степень. Укажут ли стрелки часов на это число? Однако мы должны иметь в виду, что теорема дает необходимое, но не достаточное условие.