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

Определения

Элементы теории чисел

Число называется простым, если оно не имеет других натуральных делителей, кроме 1 и .

Например, 17, 23.

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

Например: 8 и 9.

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

В общем случае . Читается сравнимо с по модулю . Это справедливо, если , где .

Отсюда называется вычетом числа по модулю , . Справедливо:

;

;

.

Использование модулярной арифметики позволяет оперировать с очень большими числами, например, при возведении в степень:

.

Малая теорема Ферма

Если ‑ простое и , то

.

Функция Эйлера

Количество положительных целых, меньших , которые взаимно просты с , определяется с помощью функции Эйлера :

Модуль	простое			( и простые)

Обобщение Эйлера малой теоремы Ферма: если , то

.

Дата добавления: 2014-12-16