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

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

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

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

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

Наприклад:

$15 \equiv 4 (\mod 11) .$

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

$16 \equiv 37 (\mod 7) .$

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

$16 \equiv - 5 (\mod 7) .$

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

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

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

$(a_{1} + a_{2}) \equiv (b_{1} + b_{2}) (\mod n)$
$(a_{1} - a_{2}) \equiv (b_{1} - b_{2}) (\mod n)$
$(a_{1} a_{2}) \equiv (b_{1} b_{2}) (\mod n) .$

Шаблон:Hider

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

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

рефлексивність $a \equiv a (\mod n) .$
симетричність $a \equiv b (\mod n) ⟺ b \equiv a (\mod n) .$
транзитивність: якщо $a \equiv b (\mod n)$ та $b \equiv c (\mod n)$ , то також $a \equiv c (\mod n) .$

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

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

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

Для прикладу, розглянемо відношення по модулю 2. $a \equiv b (\mod 2)$ , тоді і тільки тоді, коли їх різниця $a - b$ парне число. Це співвідношення призводить до двох класів еквівалентності: один клас, що складається з усіх парних чисел, та другий, який складається з усіх непарних чисел. Клас парних чисел позначається, як Шаблон:Math, непарних як Шаблон:Math. Згідно з цим співвідношенням Шаблон:Math, Шаблон:Math та Шаблон:Math належать одному класу — $[0] = {\overline{0}}_{2} = {0, \pm 2, \pm 4, \pm 6, \dots}$ .

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

ℤ / n ℤ = {{\overline{a}}_{n} | a \in ℤ} .

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

ℤ / n ℤ = {{\overline{0}}_{n}, {\overline{1}}_{n}, {\overline{2}}_{n}, \dots, {\overline{n - 1}}_{n}} .

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

${\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{(a b)}}_{n} .$

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

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

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

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

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

a n + b m \equiv 1 (\mod n)

і як наслідок

b m \equiv 1 (\mod n) .

Навпаки, якщо $b m \equiv 1 (\mod n)$ для деякого $b$ , то $a n + b m = 1$ для деякого $a$ , що неможливо, враховуючи взаємну простоту m i n.

Відповідно, якщо $n$ просте число, то $ℤ / n ℤ$ є полем.

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

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

a \cdot x \equiv b (\mod n) .

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

x \equiv b \cdot a^{φ (n) - 1} (\mod n),

якщо НСД

(a, n) = 1,

тобто взаємно прості числа.

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

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

2 \cdot x \equiv 3 (\mod 4)

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

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

4 \cdot x \equiv 6 (\mod 22)

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

x = 7, x = 18 .

Див. також

Джерела

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

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

Зміст

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

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

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

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

Див. також

Джерела

Навігаційне меню

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

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

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

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

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

Див. також

Джерела

Навігаційне меню

Пошук