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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Операції з часом на цих часах використовують правила арифметики по модулю 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.

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

В сучасному вигляді модульна арифметика була розвинута Гаусом в Arithmetical Investigations[en] (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.\,


Рівність за модулем, як відношення еквівалентності[ред.ред. код]

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

Тобто відношення рівності за модулем є відношенням еквівалентності на множині цілих чисел \Z. Тоді \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]. Згідно з цим співвідношенням [7], [9], та [117] належать одному класу - \overline{0}_n=\left\{0, 0 \pm 2, \pm 4,\pm 6, \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 є полем.

Розв'язання лінійних рівнянь[ред.ред. код]

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

a \cdot x \equiv b \pmod n.

Розв'язання можна отримати безпосередньо діленням x\equiv\frac ba \pmod n або за допомогою формули

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

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

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

2 \cdot x \equiv 3 \pmod 4

не має рішення на множині натуральних чисел.

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

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

має два рішення

x = 7, \; x = 18.

Див. також[ред.ред. код]

Література[ред.ред. код]