Калькулятор модульної арифметики

Модульна арифметика — розділ теорії чисел, що вивчає операції над цілими числами з «обгортанням» за фіксованим модулем n. Вона є фундаментом сучасної криптографії (RSA, еліптичні криві), хеш-функцій та контрольних сум. Цей калькулятор обчислює a mod n, обернений елемент за модулем через розширений алгоритм Евкліда, а також суму та добуток двох чисел за модулем — із детальним покроковим розв'язанням.

Даний інструмент реалізує науково обґрунтований підхід до обчислень, що базується на перевірених алгоритмах теорії чисел, зокрема розширеному алгоритмі Евкліда. Усі розрахунки виконуються у реальному часі безпосередньо у браузері — без відправки даних на сервер і без необхідності встановлювати додаткове програмне забезпечення. Інтерфейс оптимізований для зручного введення параметрів, відображення результатів з покроковими поясненнями застосованих формул.

Розрахунок за модулем

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

Остача від ділення (a mod n)

a = q·n + r, де 0 ≤ r < n q = floor(a / n) (ціла частина, округлена вниз) r = a mod n = a − q·n

Обернений елемент за модулем

a⁻¹ mod n існує тоді і лише тоді, коли gcd(a, n) = 1 Розширений алгоритм Евкліда знаходить x, y: a·x + n·y = gcd(a, n) = 1 Тоді a⁻¹ mod n = x mod n

Додавання та множення за модулем

(a + b) mod n = ((a mod n) + (b mod n)) mod n (a × b) mod n = ((a mod n) × (b mod n)) mod n

Важливі зауваження

  • Модуль n — має бути додатним цілим числом (n > 0), інакше операція не визначена
  • Обернений елемент — існує лише коли gcd(a, n) = 1 (a і n взаємно прості); інакше калькулятор покаже «не існує»
  • Від'ємні числа — результат a mod n завжди невід'ємний (0 ≤ r < n), на відміну від оператора % у деяких мовах програмування
  • Точність — обчислення виконуються у форматі подвійної точності JavaScript, коректні для цілих чисел приблизно до 2⁵³
  • Ціле a — саме число a не обмежене діапазоном 0..n−1, воно приводиться до цього діапазону автоматично

Приклади розв'язання

Покрокові задачі

Приклад 1: Обчисліть 17 mod 5.

Розв'язання:

q = floor(17 / 5) = 3

r = 17 − 3 × 5 = 17 − 15 = 2

Відповідь: 17 mod 5 = 2, оскільки 17 = 3 × 5 + 2

Приклад 2: Знайдіть обернений елемент 3⁻¹ mod 11.

Розв'язання (розширений алгоритм Евкліда):

11 = 3 × 3 + 2

3 = 1 × 2 + 1

2 = 2 × 1 + 0 → gcd(3, 11) = 1, обернений елемент існує

Зворотний хід: 1 = 3 − 1 × 2 = 3 − 1 × (11 − 3 × 3) = 4 × 3 − 1 × 11

Відповідь: x = 4. Перевірка: 3 × 4 = 12 = 1 × 11 + 1, тобто 12 mod 11 = 1. Отже, 3⁻¹ mod 11 = 4

Приклад 3: Обчисліть (8 + 9) mod 7 та (8 × 9) mod 7.

Розв'язання:

8 + 9 = 17; 17 mod 7: q = floor(17/7) = 2, r = 17 − 2×7 = 3

8 × 9 = 72; 72 mod 7: q = floor(72/7) = 10, r = 72 − 10×7 = 2

Відповідь: (8 + 9) mod 7 = 3, (8 × 9) mod 7 = 2

Практичне значення та контекст

Де застосовується

Модульна арифметика лежить в основі криптографічних алгоритмів з відкритим ключем (RSA, Діффі-Геллман, еліптичні криві), хеш-таблиць і контрольних сум (перевірка ISBN, IBAN, номерів банківських карток за алгоритмом Луна). Студенти використовують такі калькулятори для перевірки домашніх завдань з теорії чисел та дискретної математики, а розробники — для дебагу криптографічного коду і генераторів псевдовипадкових чисел. Простота доступу через браузер робить цей інструмент зручним як для навчання, так і для швидкої перевірки обчислень.

Часті запитання (FAQ)

Що таке модульна арифметика?
Модульна арифметика — це система арифметики для цілих чисел, у якій числа «обгортаються» після досягнення певного значення — модуля n. Два числа вважаються рівними за модулем n, якщо їхня різниця ділиться на n без остачі. Її часто називають «арифметикою годинника», бо циферблат з 12 годин — приклад модульної арифметики за модулем 12.
Що означає "a mod n"?
Вираз a mod n позначає залишок від ділення числа a на n, і завжди лежить у діапазоні від 0 до n−1. Формально a = q·n + r, де q — ціла частина від ділення (частка), а r = a mod n — остача. Для від'ємних a використовується математичне означення остачі, яка залишається невід'ємною.
Як знайти обернений елемент за модулем?
Обернений елемент a⁻¹ mod n — це таке число x, що a·x ≡ 1 (mod n). Він існує лише тоді, коли gcd(a, n) = 1, тобто a і n взаємно прості. Знайти його можна за допомогою розширеного алгоритму Евкліда, який знаходить цілі x та y такі, що a·x + n·y = gcd(a, n) = 1, після чого x mod n і є шуканим оберненим елементом.
Де застосовується модульна арифметика?
Модульна арифметика — основа сучасної криптографії: алгоритми RSA, Діффі-Геллмана та еліптичних кривих використовують операції за модулем для шифрування і цифрових підписів. Вона також лежить в основі хеш-функцій, контрольних сум (наприклад, ISBN та банківських карток), генераторів псевдовипадкових чисел та обчислень з датами й календарями (дні тижня, високосні роки).
Які типові помилки допускають при обчисленнях за модулем?
Найчастіша помилка — плутанина між математичним остачею і оператором % у мовах програмування, який для від'ємних чисел може повертати від'ємний результат. Інша поширена помилка — спроба знайти обернений елемент, коли a і n не взаємно прості (gcd(a, n) ≠ 1), тоді оберненого елемента не існує. Також забувають, що додавання й множення за модулем виконуються над результатом операції, а не над проміжними доданками окремо.

📁 Категорія: Математика