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

(Перенаправлено з Кільце залишків)

Мо́дульна арифме́тика — це система арифметики цілих чисел, в якій числа «обертаються навколо» деякого значення — модуля.

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