96 Глава 7. ЭЛЕМЕНТЫ ТЕОРИИ СРАВНЕНИЙ

При формировании очередной строки остаток r4 =0 . Выписываем решение из данных предыдущего шага:

НОД(25,15)= r3 = 5 , x = x3 = −1 y = y3 = 2 , xr0 + yr1 = −25 +30 = 5 = НОД(25,15).

7.2. Модульная арифметика

Каждое целое число a можно разделить с остатком на натуральное число

m : a = km +r 0 ≤ r < m .

Остаток от деления числа на m называется вычетом (в данном случае - вычетом числа a по модулю m). Операция, сопоставляющая числу a его вычет по модулю m, называется приведением a по модулю m.

Определение. Два целых числа a и b сравнимы по модулю m, если их разность делится на m. Аналогия – тело, движущееся по окружности, периодически попадает в одну и ту же точку окружности, хотя проходит разный путь. Длины путей «сравнимы по модулю длины окружности».

Отношение	сравнимости	записывается в	виде: a ≡b(modm),
a ≡bmodm ,	a ≡b(m). Вместо	знака сравнения	часто используется знак

равенства. Кроме того, если это не вызывает недоразумений, указание модуля может отсутствовать.

В соответствии с данным определением числа, имеющие одинаковые остатки от деления на m, сравнимы по модулю m.

Если не оговорено противное, то стандартные значения вычетов по модулю m, принадлежат множеству 0,1,Km −1 (т.н. система наименьших неотрицательных вычетов).

Вычет суммы по модулю m равен сумме вычетов, приведенной при необходимости еще раз по модулю m. Аналогичным свойством обладает вычет

a−1 .

Модульная арифметика 97

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

Алгоритм Эвклида показывает, что для взаимно простых чисел a и m

всегда существует число b такое, что ab ≡1modm.

Такое число называется обратным к a по модулю m и обозначается Рассмотрим степени числа a по модулю m, где a и m взаимно просты.

Пусть m=11. Вычеты степеней числа 2 для показателей 0,1,2,…,10 таковы: 1,2,4,8,5,10,9,7,3,6,1. Аналогично, те же степени числа 3 сравнимы соответственно с числами 1,3,9,5,4,1,3,9,5,4,1. В каждом случае имеется периодичность.

Пусть	(a,m)=1. Наименьшее натуральное число δ ,	такое,	что
aδ ≡1mod m	по модулю m, называется порядком (показателем)	числа	a по
модулю m. Порядок числа a по модулю m обозначается ordma .

7.2.1. Функция Эйлера и малая теорема Ферма

Порядки чисел по модулю m различны. Существуют числа, являющиеся порядками одновременно для всех вычетов, взаимно простых с m. Одно из таких чисел равно значению т.н. функции Эйлера ϕ(m), определяемой как количество чисел в последовательности 1,Km −1,m , взаимно простых с m.

Из этого свойства немедленно вытекает, что порядок каждого вычета делит ϕ(m). Также очевидно, что при простом p , ϕ(p)= p −1.

Функция Эйлера является мультипликативной: если (a,b)=1, то

ϕ(ab)=ϕ(a)ϕ(b) и ϕ(1)=1.

Пусть m = p1a p2b Kpst , тогда ϕ(m)= p1a−1 p2b−1Kpst−1(p1 −1)K(ps −1).