Калькулятор теорії чисел — прості числа, НСД/НСК, модульна арифметика та інше
Калькулятор теорії чисел
Досліджуйте прості числа, розкладання на множники, найбільші спільні дільники, модульну арифметику та інше. Усі обчислення виконуються локально у вашому браузері — ваші дані ніколи не вивантажуються.
Режим:
Перевірка простоти числа
Введіть число і натисніть «Перевірити»
Порада: використовується детермінований тест Міллера-Рабіна для чисел до 264. Натисніть «Наступне просте» або «Попереднє просте», щоб знайти найближчі прості числа.
Розкладання на прості множники
Введіть число і натисніть «Розкласти»
Порада: підтримує цілі числа до 1015. Розклад дерева множників у вигляді простих степенів.
Калькулятор НСД і НСК
Введіть числа і натисніть НСД, НСК або обидва
Порада: введіть 2 або більше цілих чисел через кому. НСД обчислюється алгоритмом Евкліда; НСК — як |a*b|/(a,b).
Модульна арифметика
Введіть a, b, m і натисніть операцію
Порада: модульне піднесення до степеня використовує швидке піднесення (квадрат-і-множення). Модульна обернена існує лише тоді, коли a і m взаємно прості.
Дільники і функції дільників
Введіть число і натисніть «Обчислити»
Порада: виводить усі додатні дільники, кількість дільників d(n), суму дільників σ(n) і власні дільники. Підтримує числа до 1012.
Функція Ойлера та арифметичні функції
Введіть число і натисніть «Обчислити»
Порада: обчислює функцію Ойлера φ(n), функцію Мебіуса μ(n), σ(n), d(n) та пов'язані арифметичні функції.
Прості числа та порівняння
Просте число має рівно два дільники: 1 і саме себе; кожне ціле число, більше за 1, розкладається на прості єдиним способом (основна теорема арифметики). Порівняння a ≡ b (mod n) означає, що n ділить a−b — арифметика на циферблаті годинника, де 10 + 5 ≡ 3 (mod 12), і основа НСД, НСК і модульного піднесення до степеня.
Перемноження двох великих простих чисел миттєве, але відновлення їх з добутку обчислювально надважке — саме ця однобічна асиметрія лежить в основі шифрування RSA, і саме тому φ(n) для 2048-бітного модуля не є публічним.
