Составители:
Как известно, набор целых чисел от 0 до n - 1 называют полным
набором вычетов по модулю n, поэтому для любого целого числа a>0 его
вычет r = a (mod n) - это некоторое целое число в интервале от 0 до n - 1.
Выделим из полного набора вычетов подмножество вычетов, взаимно
простых с n . Такое подмножество называют приведенным набором
вычетов.
Пример ΙΙ [17]. Пусть модуль n = 10, тогда полный набор вычетов по
модулю (n - 1) равен {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10.
Поэтому приведенный набор вычетов по модулю 10 равен (1, 3, 7, 9). При
формировании этого приведенного набора были удалены 6 элементов (0
и элементы кратные 2 и 5).
Для произведения простых чисел p ⋅ q
приведенный набор вычетов
имеет (p - 1)(q - 1) элементов.
Произведение (p - 1)(q - 1) = ϕ(n) называется функцией Эйлера.
При n = p ⋅ q = 2 ⋅ 5 = 10 число элементов в приведенном наборе
ϕ(n) = (p – 1)(q – 1) = (2 – 1)( 5 – 1) = 4.
Пусть n =27, тогда приведенный набор вычетов по модулю 27 = 3
3
имеет 18 элементов:
{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}.
Из полного набора вычетов исключены элементы, кратные 3. Для
модуля в виде простой степени n
r
приведенный набор вычетов
определяется из выражения
ϕ(n) = n
r-1
(n - 1).
Например, для n = 3 и r = 3 получаем 3
3-1
(3-1) = 3
2
⋅ 2 = 18.
Подводя итог изложенному можно сделать вывод, что функция
Эйлера ϕ(n) определяет число элементов в приведенном наборе вычетов
(табл. П.1)
Иначе говоря, функция ϕ(n) – это количество положительных целых,
меньших n , которые взаимно просты с n. Согласно малой теореме
Ферма: если n - простое и НОД (a, n) = 1, то
a
n-1
≡ 1 (mod n) или a
ϕ(n)
≡ 1 (mod n).
Рассмотрим три метода нахождения обратной величины вида
a
-1
≡ 1 (mod n).
157
Страницы
- « первая
- ‹ предыдущая
- …
- 153
- 154
- 155
- 156
- 157
- …
- следующая ›
- последняя »
