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

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

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

;

;

.

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

.

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

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

.