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

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

Операції з часом на цих годинниках використовують правила арифметики по модулю 12. 9+4 ≡ 1 mod 12.

Найбільш відомий приклад модульної арифметики — це запис часу в 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 записують так:

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

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

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

Наприклад:

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

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

• ${\displaystyle \ 16\equiv 37{\pmod {7}}.}$

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

• ${\displaystyle \ 16\equiv -5{\pmod {7}}.}$

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

Властивості, що виконуються для відношення рівності, виконуються також для рівності за модулем.

Якщо ${\displaystyle a_{1}\equiv b_{1}{\pmod {n}}}$ та ${\displaystyle a_{2}\equiv b_{2}{\pmod {n}}}$, тоді:

• ${\displaystyle (a_{1}+a_{2})\equiv (b_{1}+b_{2}){\pmod {n}}\,}$
• ${\displaystyle (a_{1}-a_{2})\equiv (b_{1}-b_{2}){\pmod {n}}\,}$
• ${\displaystyle (a_{1}a_{2})\equiv (b_{1}b_{2}){\pmod {n}}.\,}$

Доведення.  

Справді нехай ${\displaystyle a_{1}=ln+k,\;b_{1}=mn+k,\;a_{2}=sn+r,\;b_{2}=tn+r.}$

Тоді ${\displaystyle a_{1}+a_{2}=(l+s)n+k+r\equiv k+r{\pmod {n}}}$ і ${\displaystyle b_{1}+b_{2}=(m+t)n+k+r\equiv k+r{\pmod {n}}}$

Також ${\displaystyle a_{1}-a_{2}=(l-s)n+k-r\equiv k-r{\pmod {n}}}$ і ${\displaystyle b_{1}-b_{2}=(m-t)n+k-r\equiv k-r{\pmod {n}}}$

У випадку добутку ${\displaystyle a_{1}a_{2}=(ls)n^{2}+(lr+sk)n+kr\equiv kr{\pmod {n}}}$ і ${\displaystyle b_{1}b_{2}=(mt)n^{2}+(mr+tk)n+kr\equiv kr{\pmod {n}}}$.

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

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

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

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

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

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

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

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

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

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

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

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

• ${\displaystyle {\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.}$

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

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

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

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

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

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

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

Відповідно, якщо ${\displaystyle n}$ просте число, то ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ є полем.

Розв'язування лінійних рівнянь

Лінійне рівняння записується у вигляді

${\displaystyle a\cdot x\equiv b{\pmod {n}}.}$

Розв'язок можна отримати безпосередньо діленням ${\displaystyle x\equiv {\frac {b}{a}}{\pmod {n}}}$ або за допомогою формули

${\displaystyle x\equiv b\cdot a^{\varphi (n)-1}{\pmod {n}},}$ якщо НСД ${\displaystyle (a,n)=1,}$ тобто взаємно прості числа.

Функція ${\displaystyle \varphi (n)}$ — функція Ейлера, яка дорівнює кількості натуральних чисел, не більших n і взаємно простих з ним.

Якщо НСД ${\displaystyle (a,n)\not =1}$, порівняння або має не єдиний розв'язок, або не має розв'язків. Як легко побачити, порівняння

${\displaystyle 2\cdot x\equiv 3{\pmod {4}}}$

не має розв'язків на множині натуральних чисел.

Інше порівняння

${\displaystyle 4\cdot x\equiv 6{\pmod {22}}}$

має два розв'язки

${\displaystyle x=7,\;x=18.}$

Див. також

• Ділення з остачею
• Квадратичний закон взаємності
• Остача
• Подільність
• Символ Лежандра
• Символ Якобі

Джерела

• Дрозд Ю. А. (1997). Теорія алгебричних чисел (PDF). Київ: РВЦ “Київський університет„. с. 82. ISBN . (укр.)
• Виноградов И. М., Основы теории чисел [ 17 грудня 2004 у Wayback Machine.], М.: ГИТТЛ, 1952.
• Виленкин Н. Я., Сравнения и классы вычетов [ 4 листопада 2007 у Wayback Machine.], Квант, № 10, 1978.