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

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

 

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

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

 

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

 

Див. такожРедагувати

ЛітератураРедагувати