Том 3. Простые числа. Долгая дорога к бесконечности - страница 29
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 раз — все равно что умножить его на единицу столько же раз. Другими словами,
8>514
Гаусс заметил, что если циферблат его часов содержит простое количество чисел, р, то они будут повторяться каждые р раз, то есть они образуют повторяющиеся группы из р чисел. Тогда Гаусс переформулировал малую теорему Ферма в терминах модульной арифметики:
«Если р — простое число, то для любого натурального числа а а>р
Или, что то же самое, (а>р — а) кратно р. Например, З>5 —3 = 240, и 240 кратно 5. В терминах «часов Гаусса» теорему можно интерпретировать следующим образом. Предположим, мы хотим знать, является ли р простым числом. Построим часы с циферблатом, содержащим р делений. Возьмем любое число на циферблате, возведем его в степень р и проверим, будет ли стрелка указывать на то же число. Если нет, то мы можем быть уверены, что р не является простым числом. Например, пусть р равно 6. Построим часы с циферблатом, содержащим 6 делений. Возьмем одно из чисел, например, 4. Запишем 4>6 = 4096, что при делении на 6 дает в остатке 4.
Иначе говоря, стрелки часов делают круг за кругом, пока не остановятся на цифре 4. Мы знаем, что по малой теореме Ферма число 6 не является простым. Возьмем теперь простое число, например, 7, и посмотрим, что произойдет, когда мы возведем некоторое число в седьмую степень. Укажут ли стрелки часов на это число? Однако мы должны иметь в виду, что теорема дает необходимое, но не достаточное условие.
Это означает, что если при проверке числа а стрелки укажут на это число а, существует вероятность, что число р окажется простым. Но одной такой проверки недостаточно. Чем больше проверок мы сделаем, тем больше шанс, что число р является простым, но мы не можем утверждать это наверняка. Как мы увидим в седьмой главе, это один из способов, широко используемый современными компьютерами для определения простоты больших чисел.
Услышав выражение «мнимые числа», человек, далекий от математики, может подумать, что это еще одна причуда математиков, и будет недалек от истины. Такое мнение разделяли и многие специалисты в области математики, когда им встречались числа настолько экзотические, что к ним относились почти как к призракам.
Но эти призраки настойчиво появлялись при решении уравнений, и вскоре их стало невозможно игнорировать. Их начали использовать при расчетах, и в конце концов они были приняты в качестве решений уравнений и приобрели собственный статус, став одним из фундаментальных понятий в математике и важнейшей темой многих учебников. Было бы неправильно полагать, что они появляются лишь в мире чистой математики. На самом деле мнимые числа являются основным инструментом современной физики и самым различным образом применяются на практике.