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

Модульна арифметика — це система арифметики цілих чисел, пов'язана з залишками від ділення цілих чисел на певне задане натуральне число. Фактично в ній розглядаються класи еквівалентності певного натурального числа.

Рівність за модулем

Два числа a і b називаються рівними (конгруентними) за модулем n, якщо при діленні на n вони мають однакові залишки, тобто їхня різниця a-b ділиться на n. Для зображення цього факту використовується позначення:

$\ a\equiv b\pmod n.$

Приклади

• $\ 15\equiv 4\pmod {11}.$

Справді 15 - 4 = 11 і 11 очевидно ділиться на 11.

• $\ 16\equiv 37\pmod 7.$

Маємо 16 - 37 = -21 і -21 ділиться на 7.

• $\ 16\equiv -5\pmod 7.$

У цьому разі 16-(-5)=16+5=21 і 21 ділиться на 7.

Властивості рівності за модулем

Відразу з визначення одержуємо такі властивості:

• рефлексивність $\ a\equiv a\pmod n.$
• симетричність $\ a\equiv b\pmod n \quad \iff \quad \ b\equiv a\pmod n.$
• транзитивність: якщо $\ a\equiv b\pmod n$ та $\ b\equiv c\pmod n$ то також $\ a\equiv c\pmod n.$

Тобто відношення рівності за модулем є відношенням еквівалентності.

Також в модулярній арифметиці зберігаються деякі правила звичайної арифметики.

Якщо $a_1 \equiv b_1 \pmod n$ і $a_2 \equiv b_2 \pmod n$, тоді:

• $(a_1 + a_2) \equiv (b_1 + b_2) \pmod n\,$
• $(a_1 - a_2) \equiv (b_1 - b_2) \pmod n\,$
• $(a_1 a_2) \equiv (b_1 b_2) \pmod n.\,$

Справді нехай $a_1 = ln+k, \; b_1 = mn+k, \; a_2 = sn+r, \; b_2 = tn+r.$

Тоді $a_1+a_2 =(l+s)n+k+r\equiv k+r \pmod n$ і $b_1+b_2 =(m+t)n+k+r\equiv k+r \pmod n$

Також $a_1-a_2 =(l-s)n+k-r\equiv k-r \pmod n$ і $b_1-b_2 =(m-t)n+k-r\equiv k-r \pmod n$

У випадку добутку $a_1 a_2 =(l s)n^2+(l r+s k)n+kr\equiv kr \pmod n$ і $b_1 b_2=(m t)n^2+(m r+t k)n+kr\equiv kr \pmod n$.

В усіх трьох випадках бачимо, що остаточні вирази рівні.

Кільце класів рівності за модулем

Клас еквівалентності відношення рівності за модулем n до якого належить число a позначається $\overline{a}_n.$ До складу цього класу входять числа $\left\{\ldots, a - 2n, a - n, a, a + n, a + 2n, \ldots \right\}.$ Множина класів конгруентності за модулем $n$ позначається: $\Z/n\Z$ (або, $\Z/n$ чи $\Z_n$) і за визначенням це:

$\Z/n\Z = \left\{ \overline{a}_n | a \in \Z\right\}.$

Коли n ≠ 0, $\Z/n\Z$ має n елементів, і може бути записано:

$\Z/n\Z = \left\{ \overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n-1}_n \right\}.$

Для цих класів можна задати операції додавання, віднімання, множення:

• $\overline{a}_n + \overline{b}_n = \overline{(a + b)}_n$
• $\overline{a}_n - \overline{b}_n = \overline{(a - b)}_n$
• $\overline{a}_n \overline{b}_n = \overline{(ab)}_n.$

Обґрунтованість цих означень випливає із властивостей попереднього розділу.

Таким чином $\mathbb{Z}/n\mathbb{Z}$ є комутативним кільцем. Наприклад в $\mathbb{Z}/24\mathbb{Z}$, маємо

$\overline{12}_{24} + \overline{21}_{24} = \overline{9}_{24}$

Деякий елемент $\overline{m}_{n}$ має обернений елемент тоді і лише тоді коли m i n є взаємно простими числами. Справді, якщо m i n є взаємно простими, то тоді існують $a,b \in \mathbb{Z}$ такі, що $an+bm=1.\;$ Звідси:

$an+bm\equiv 1 \pmod n$ і як наслідок $bm\equiv 1 \pmod n.$

Навпаки, якщо $bm\equiv 1 \pmod n$ для деякого $b$, то $an+bm=1\;$ для деякого $a$, що неможливо, враховуючи взаємну простоту m i n. Відповідно, якщо $n$ просте число, то $\Z/n\Z$ є полем.

Див. також

• Арифметика
• Остача
• Подільність

Література

• Виноградов И. М., Основы теории чисел, М.: ГИТТЛ, 1952.
• Виленкин Н. Я., Сравнения и классы вычетов, Квант, № 10, 1978.