Модульна арифметика: що це таке і де застосовується

Модуляції

(7 + 7) mod 12 = (14) mod 12 = 2 mod 12 [2 – це залишок, коли 14 ділиться на 12. Рівняння 14 mod 12 = 2 mod 12 означає, що 14 годин і 2 години виглядають однаково на 12-годинних годинах. Вони є конгруэнтными, позначеними знаком потрійної рівності: 14 ≡ 2 mod 12.

Інший приклад: зараз 8:00. Де буде велика стрілка через 25 годин?

Замість додавання 25 до 8, ви можете зрозуміти, що 25 годин – це просто «1 день + 1 годину». Відповідь проста. Отже, годинник закінчаться на 1 годину вперед – 9:00.

(8 + 25) мод 12 ≡ (8) мод 12 + (25) мод 12 ≡ (8) мод 12 + (1) мод 12 ≡ 9 мод 12. Ви інтуїтивно конвертували 25 в 1 і додали це до 8.

Використовуючи годинник в якості аналогії, ми можемо з’ясувати, чи працюють правила модульної арифметики, а вони працюють.

Додавання/Віднімання

Припустимо, два рази виглядають однаково на наших годинниках («2:00» та «14:00»). Якщо ми додамо однакові х годин до обом, що станеться? Ну, вони змінюються на ту ж суму на годиннику! 2:00 + 5 годин ≡ 14:00 + 5 годин – обидва покажуть 7:00.

Навіщо? Ми можемо просто додати 5 до 2 залишках, які обидва мають, і вони просуваються однаково. Для всіх конгруентних чисел (2 та 14) додавання і віднімання мають однаковий результат.

Важче зрозуміти, залишається множення таким же. Якщо 14 ≡ 2 (мод 12), ми можемо помножити обидва числа і отримати однаковий результат? Давайте подивимося, що станеться, коли ми помножимо на 3.

Ну, 2:00 * 3 × 6:00. Але що таке 14:00 * 3?

Пам’ятайте, 14 = 12 + 2. Отже, ми можемо сказати,

14 * 3 = (12 + 2) * 3 = (12 * 3) + (2 * 3)

Першу частину (12 * 3) можна ігнорувати! Переповнення 12 годин, яке несе 14, просто повторюється кілька разів. Але кого це хвилює? У будь-якому випадку ми ігноруємо переповнення.