Том 3. Простые числа. Долгая дорога к бесконечности | страница 46

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^>514 

1 (mod 7).

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

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

а (mod р)».

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