Шукати в цьому блозі

четвер, 18 лютого 2016 р.

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


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

Немає коментарів:

Дописати коментар

Примітка: лише член цього блогу може опублікувати коментар.

Підписатися на: Дописати коментарі (Atom)