Любое соотношение, имеюш;ееся между целыми числами или дробями обычной арифметики, остается верным и при интерпретации в новой арифметике. Например, соотношение

1 2 7 23 ~ 6

по mod И переходит в

6 + 8 = 3,

потому что решением сравнения 2х = 1 является х = 6, решением сравнения 6х = 7 является :г = 3, а решением сравнения Зх = 2 является х = 8, Естественно, что интерпретация дробей зависит от модуля, например

- = 8 (mod 11), но - = 3 (mod 7).

Уже отмечалось, что на эти вычисления накладывается единственное ограничение: знаменатель каждой дроби должен быть взаимно прост с модулем. Если модуль простой (как это было в примерах с модулем 11), то указанное ограничение принимает совсем простой вид: знаменатель не должен быть сравним с О (mod ш), что в точности аналогично требованию обычной арифметики, в которой знаменатель всегда отличен от 0. Мы егце вернемся к этому вопросу (п. 7).

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

Возьмем число х и рассмотрим его степени х, х, х, ... Так как для них имеется лишь конечное число возможностей по модулю ш, то на некотором месте должна стоять степень, уже встречавшаяся ранее; пусть, скажем,

х = х (mod ш),

где к < h. Если х взаимно просто с ш, на множитель х можно сократить, значит, в этом случае х = 1 (mod ш), где / = - h - к. Отсюда следует, что каждое число х, взаимно простое с т, удовлетворяет некоторому сравнению такого вида. Наи-

3] ТЕОРЕМА ФЕРМА 45

меньший показатель /, для которого 1 (mod ш), называется порядком X по модулю т. Если х равен 1, его порядок, очевидно, также равен 1. Для иллюстрации этого определения вычислим порядки нескольких элементов по модулю И. Степени 2, взятые по модулю И, таковы:

2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, ...

Каждая из них есть удвоенная предыдугцая, из которой вычитается И или кратное И, если после умножения на два получается число, большее И. Первая степень 2, сравнимая с 1, равна 2, значит, порядок 2 (mod И) равен 10. В качестве другого примера рассмотрим степени 3:

3, 9, 5, 4, 1, 3, 9, ...

Первая степень 3, сравнимая с 1, есть 3, так что порядок 3 (mod И) равен 5. Можно найти, что порядок 4 равен 5, таков же и порядок 5.

Легко заметить, что последовательные степени х периодичны; если мы достигли первого числа /, для которого = 1, то х = и предыдугций цикл повторяется. Ясно, что х = = l(mod т) тогда и только тогда, когда п кратно порядку х. В последнем примере 3 = 1 (mod 11) тогда и только тогда, когда п кратно 5. Так как 3 = 1, то это верно и для п = 0; это верно и для отрицательных показателей, если 3~ или интерпретируется описанным в п. 2 способом как дробь по mod И. Отрицательные степени 3 (mod И) получаются чтением ряда положительных степеней в обратном порядке, так что таблица степеней 3 по модулю И имеет вид

п = ... -3 -2 -1 О 1 2 3 4 5 6... 3 = ... 9 5 41395413...

Ферма заметил, что если модуль простой, скажем р, то каждое целое не сравнимое с О, удовлетворяет сравнению

х- = 1 (mod р). (3)

Ввиду сказанного ранее этот факт эквивалентен утверждению: порядок любого числа является делителем р - 1. Результат (3) был сформулирован Ферма в письме к Френиклю де Бесси (Frenicle de Bessy) 18 октября 1640 года; в этом письме Фер-

ма утверждал также, что обладает доказательством указанного факта. Но, как и в большинстве открытий Ферма, доказательство не было опубликовано и не сохранилось. Первое известное доказательство, по-видимому, принадлежит Лейбницу (1646- 1716). Лейбниц доказал, что имеет место сравнение

= X (mod р),

эквивалентное (3), представив х в виде суммы 1 + 1 + ... + 1 из X единиц {х предполагается положительным) и затем раскрыв (1 + 1 + ... + 1) по полиномиальной теореме. Члены F + F + +... + Р дают р; кроме того, легко доказать, что биномиальные коэффициенты при остальных членах делятся на р.

Совершенно другое доказательство было дано в 1806 году Ивори (Ivory). Если

X фО (mod р),

то целые числа

X, 2х, Зх, ..., {р - 1)х сравнимы (в некотором порядке) с числами 1, 2, 3, ..., р - 1, так как каждое из этих множеств представляет собой полную систему вычетов, за исключением 0. Так как все элементы этих множеств, взятые в некотором порядке, сравнимы друг с другом, то сравнимы и их произведения, поэтому

X 2х Зх ,,, {р - 1)х = 1 2 3 ... {р - 1) (mod р).

Сокрагцая на множители 2, 3, ..., р - 1 (что допустимо), мы получаем (3).

Одно из достоинств этого доказательства состоит в том, что оно может быть перенесено на более обгций случай непростого модуля. Обобгцение результата (3) на любой модуль впервые дал Эйлер в 1760 году. Прежде чем формулировать полученный им результат, рассмотрим вопрос о том, сколько чисел в ряду О, 1, 2, ..., ш - 1 взаимно просто с т. Обозначим количество этих чисел через (f{m). Если т простое, то все числа в этом ряду, за исключением О, взаимно просты с ш, так что (f{p) = р - 1 для любого простого р. Эйлеровское обобгцение теоремы Ферма для любого модуля от таково:

М = 1 (modm), (4)

если X взаимно просто с т.