Малая теорема Ферма (1640).

Если — простое число и а — произвольное целое число, не делящееся на , то .

Доказательство. Рассмотрим числа . Никакие два из этих чисел не дают при делении на m одинаковых остатков. [Если бы остатки были одинаковы, то было бы кратно потому что при вычитании остатки сокращаются; так как не делит а, то m делило бы , что невозможно, поскольку принадлежат последовательности Поэтому при делении на числа дают остатки в каком-то порядке, где 0 получается при делении на пуская, имеем . Вычитая правую часть равенства из левой, получаем , откуда следует, что делится на т. Так как не делит и является простым числом, то m делит

Следствие 2.3.13. Если m — простое число, то в кольце выполняется равенство

Следующее утверждение, принадлежащее Эйлеру, обобщает малую теорему Ферма ( — не обязательно простое число).

Теорема 2.3.14 (Эйлер). Если , то

Доказательство. Доказательство ведется параллельно доказательству теоремы Ферма. Рассмотрим простую систему остатков по модулю и домнажим каждое на а, где (Эта система остатков называется «простой», потому что она состоит из остатков, взаимно простых с m и образующих мультипликативную группу.) Домножение изменяет последовательность остатков, но не меняет их общего произведения, так как остатки образуют мультипликативную группу. Следовательно, . Поскольку по определению остатки взаимно просты , мы можем применить правило сокращения из теоремы 2.3.7, после чего получим

Следствие 2.3.15. В кольце из вытекает, что

Из сказанного выше следует, что для вычисления мультипликативного обратного к а по модулю нужно возвести а в некоторую

степень к, где к может равняться либо либо Рассмотрим два способа возведения в степень.

Первый, использующий «грубую силу», требует выполнения к умножений. Поскольку мы имеем дело с арифметикой коротких чисел, то каждое умножение выполняется за время и, следовательно, все время выполнения равно [Мы воспользовались тем, что ]

Второй, так называемый «бинарный метод», является гораздо более аффективным способом возведения числа а в степень этот метод был известен в Индии 2000 лет назад. Он работает следующим образом: запишем к в двоичной системе счисления, опустив нули перед первой значащей цифрой,

Заменим каждую цифру «1» на пару букв и каждую цифру «0» на букву после этого вычеркнем пару букв слева. Получившаяся последовательность букв представляет собой правило для вычисления если интерпретировать как «возвести в квадрат и взять остаток по модулю , а как «умножить на а и взять остаток по модулю .

Пример. В для того, чтобы найти , мы должны вычислить 49, причем двоичное представление 9 равно 1001. Образуем последовательность и, вычеркнув левые получим последовательность , которая означает, что мы должны «возвести в квадрат, возвести в квадрат, возвести в квадрат и умножить на 4», выполняя, конечно, приведение по модулю И на каждом шаге; иначе говоря, Проводя вычисления, последовательно получим в выполняя последний шаг, т.е. возведение в квадрат и умножение на 4, заметим, что откуда получаем, что мультипликативный обратный к 4 по модулю 11 равен 3.

Описанная выше «бинарная» процедура работает слева направо по отношению к битовому представлению числа к и, поскольку она не использует временной памяти, хорошо подходит для аппаратной реализации. Однако удобнее работать справа налево, поскольку мы можем получать биты с помощью обычного сдвига вправо на единицу. Следующий алгоритм использует приведенные выше идеи и работает справа налево.

Е. Возвести в степень (Exponentiate)

Вход: Ненулевые а, к и а — элементизйт, к совпадает либо с либо с

Выход: мультипликативный обратный к а элемент по модулю , где в кольце

1. [Инициализация] .

2. [Вычисление следующего бита] если то перейти к шагу 5.

3. [Умножить и взять остаток по модулю .

4. [Закончить?] Если то вернуть .

5. [Возвести в квадрат и взять остаток по модулю ; перейти к шагу 2.

Анализ времени работы алгоритма Е. Пусть двоичное представление числа к состоит из битов, и пусть j из них равны единице. Тогда в алгоритме выполняется умножений, каждое из которых занимает время Поскольку j не больше, чем , имеем (проверьте это) и

что является значительным улучшением по сравнению с примитивным подходом.

Предположим теперь, что мы применяем алгоритм Е к целым числам, а не к элементам кольца Пусть на вход алгоритма подаются целые числа а, b. Тогда, если мы заменим шаг 3 на и шаг 5 на и если на шаге 1 вместо мы присвоим начальное значение «В и вместо к — значение «К b», то алгоритм выдаст b. Этот удобный на практике метод выполнения умножения называют часто «русским крестьянским» методом, подразумевая, что русские крестьяне использовали его, потому что будто бы умели только умножать и делить на 2 и складывать.

Пример. Чтобы умножить 38 на 19, запишем эти числа в вершинах двух столбцов с метками а и b. Следующие элементы этих столбцов получаются умножением на 2 в столбце а и делением на 2 в столбце 6. Если число в столбце 6 нечетно, вычтем из него 1 перед делением на 2 и запишем соседнее число из столбца а в третий столбец, который называется сумма. Когда мы получим

число 1 в столбце , сложим числа в столбце сумма и получим ответ. Получается следующая таблица:

Русский крестьянский метод основан на том, что если b четно, и если нечетно.