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

Мо́дульна арифме́тика — це система арифметики цілих чисел, в якій числа «обертаються навколо» деякого значення — модуля.

Найбільш відомий приклад модульної арифметики — це запис часу в 12-годинному форматі, в якому день ділиться на два 12-годинних періоди. Якщо зараз 9:00, то через 4 години на годиннику буде 1:00. Якщо просто додати, то 9 + 4 = 13, але це неправильна відповідь, тому що на годиннику по досягненні стрілки 12-ї години, замість 12:00 ми отримуємо 00:00. Тому правильна відповідь, що на годиннику буде 1:00.

Аналогічним чином, якщо годинник починає відлік о 12:00 (опівдні) і пройде 21 година, то час буде 9:00 наступного дня, а не 33:00. Оскільки годинник починає новий відлік часу після досягнення 12, то це буде арифметика за модулем 12. 12 відповідає не тільки значенню 12, але також і 0, так що час, який називається «12:00», також може бути названий «0:00», оскільки 0 ≡ 12 mod 12.

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

У сучасному вигляді модульна арифметика була розвинута Гауссом в Disquisitiones Arithmeticae (1801).

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

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

\ a\equiv b{\pmod {n}}.

Еквівалентні визначення:

Різниця a − b ділиться на n націло. Тобто a − b = kn, де k — якесь ціле число.
Число a може бути записано у вигляді a = b + kn, де k — якесь ціле число.

Наприклад:

$\ 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_{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}=(ls)n^{2}+(lr+sk)n+kr\equiv kr{\pmod {n}}

і

b_{1}b_{2}=(mt)n^{2}+(mr+tk)n+kr\equiv kr{\pmod {n}}

.

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

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

З визначення рівності за модулем витікають такі властивості:

рефлексивність $\ 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}}.$

Тобто відношення рівності за модулем є відношенням еквівалентності на множині цілих чисел $\mathbb {Z}$ . Тоді $\mathbb {Z}$ розбивається на класи еквівалентності.

Клас еквівалентності відношення рівності за модулем n до якого належить число a позначається ${\overline {a}}_{n}$ .

Оскільки, $n\equiv 0{\pmod {n}}$ , то додати n, теж саме, що і додати 0. Тому клас числа ${\overline {a}}_{n}=\left\{a,a\pm n,a\pm 2n,a\pm 3n,\ldots \right\}=\left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}.$

Для прикладу, розглянемо відношення по модулю 2. $\ a\equiv b{\pmod {2}}$ , тоді і тільки тоді, коли їх різниця $a-b$ парне число. Це співвідношення призводить до двох класів еквівалентності: один клас, що складається з усіх парних чисел, та другий, який складається з усіх непарних чисел. Клас парних чисел позначається, як $[0]$ , непарних як $[1]$ . Згідно з цим співвідношенням $8$ , $10$ та $118$ належать одному класу — $[0]={\overline {0}}_{2}=\left\{0,\pm 2,\pm 4,\pm 6,\ldots \right\}$ .

Множина класів конгруентності за модулем $n$ позначається: $\mathbb {Z} /n\mathbb {Z}$ (або, $\mathbb {Z} /n$ чи $\mathbb {Z} _{n}$ ) і за визначенням це:

\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.

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

\mathbb {Z} /n\mathbb {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.\;$ Звідси: