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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Операції з часом на цих годинниках використовують правила арифметики по модулю 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 − b ділиться на n націло. Тобто a − b = kn, де k — якесь ціле число.
  • Число a може бути записано у вигляді a = b + kn, де k — якесь ціле число.

Наприклад:

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

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

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

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

Якщо та , тоді:

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

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

  • рефлексивність
  • симетричність
  • транзитивність: якщо та , то також

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

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

Оскільки, , то додати n, теж саме, що і додати 0. Тому клас числа

Для прикладу, розглянемо відношення по модулю 2. , тоді і тільки тоді, коли їх різниця парне число. Це співвідношення призводить до двох класів еквівалентності: один клас, що складається з усіх парних чисел, та другий, який складається з усіх непарних чисел. Клас парних чисел позначається, як [0], непарних як [1]. Згідно з цим співвідношенням 8, 10 та 118 належать одному класу — .

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

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

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

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

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

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

Деякий елемент має обернений елемент тоді й лише тоді коли m i n є взаємно простими числами. Справді, якщо m i n є взаємно простими, то тоді існують такі, що Звідси:

і як наслідок

Навпаки, якщо для деякого , то для деякого , що неможливо, враховуючи взаємну простоту m i n.

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

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

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

Розв'язок можна отримати безпосередньо діленням або за допомогою формули

якщо НСД тобто взаємно прості числа.

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

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

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

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

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

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

Джерела[ред. | ред. код]

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