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

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

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

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

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

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

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

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

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

і як наслідок

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

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

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

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

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

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

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

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

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

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

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

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