🔢

Взаимно простые числа

Проверка взаимной простоты чисел с разложением на множители и НОД

Проверка взаимной простоты чисел

Первое число:

Второе число:

Загрузка инструмента...

Калькулятор взаимно простых чисел — проверка и нахождение

Онлайн калькулятор для проверки взаимной простоты двух чисел. Инструмент находит НОД через алгоритм Евклида, раскладывает числа на простые множители и определяет, являются ли они взаимно простыми (НОД = 1). Показывает пошаговое решение и свойства числовой пары.

Проверка взаимной простоты двух чисел
Нахождение НОД алгоритмом Евклида с пошаговым решением
Разложение обоих чисел на простые множители
Нахождение коэффициентов тождества Безу (ax + by = НОД)
Определение всех общих делителей пары чисел
История расчётов с копированием результатов

Что такое взаимно простые числа

Два целых числа называются взаимно простыми, если их наибольший общий делитель (НОД) равен 1. Это означает, что у них нет общих простых множителей. Например, 15 = 3 × 5 и 28 = 2² × 7 — взаимно просты, хотя сами по себе не являются простыми числами.

Ключевые свойства: любые два последовательных числа (n и n+1) взаимно просты. Если НОД(a, b) = 1 и a делит b×c, то a делит c. Тождество Безу: если НОД(a, b) = 1, существуют целые x и y такие, что ax + by = 1.

Где используются взаимно простые числа

В криптографии — алгоритм RSA основан на взаимной простоте: открытый ключ e должен быть взаимно прост с φ(n). В теории чисел — функция Эйлера φ(n) считает количество чисел, взаимно простых с n. В программировании — хеш-таблицы с размером, взаимно простым с шагом, дают равномерное распределение. В музыке — интервалы с взаимно простыми частотами звучат консонансно.

💡

Пример из жизни

Студент-криптограф реализует алгоритм RSA. Нужно выбрать открытый ключ e, взаимно простой с φ(n) = 3120.

Проверил e = 17: ввёл пару (17, 3120) в калькулятор

Калькулятор разложил: 17 — простое число, 3120 = 2⁴ × 3 × 5 × 13

НОД(17, 3120) = 1 — числа взаимно просты, e = 17 подходит

Нашёл коэффициенты Безу: 17 × 2753 + 3120 × (−15) = 1 → закрытый ключ d = 2753

✅

Ключевая пара RSA сгенерирована корректно. Калькулятор сэкономил время на ручной проверке и нахождении обратного элемента через расширенный алгоритм Евклида.

🧠

Знаете ли вы?

🔐

Безопасность RSA-шифрования зависит от взаимной простоты — если e и φ(n) не взаимно просты, шифр взламывается мгновенно

📊

Вероятность того, что два случайных числа взаимно просты = 6/π² ≈ 60,8%. Этот результат доказал Эйлер в 1736 году

🔢

Функция Эйлера φ(12) = 4: числа 1, 5, 7, 11 взаимно просты с 12. Это основа модулярной арифметики

🧮

Алгоритм Евклида находит НОД за O(log n) шагов — для миллиардных чисел это менее 30 итераций

🎵

Октава (2:1), квинта (3:2), кварта (4:3) — музыкальные интервалы с взаимно простыми частотами звучат гармонично

⚙️

Шестерни с взаимно простыми числами зубьев изнашиваются равномерно — каждый зуб встречает каждый зуб парной шестерни

Примеры взаимно простых и не взаимно простых пар

Числа	Разложение	НОД	Взаимно просты?
8 и 15	2³ и 3×5	1	Да ✓
12 и 18	2²×3 и 2×3²	6	Нет ✗
17 и 31	простые	1	Да ✓
100 и 27	2²×5² и 3³	1	Да ✓
14 и 49	2×7 и 7²	7	Нет ✗
n и n+1	последовательные	1	Всегда да ✓

💡

Важно знать

Быстрая проверка: если одно из чисел — простое и не делит другое, числа точно взаимно просты. Также любые два последовательных числа (например, 100 и 101) всегда взаимно просты — это следует из свойств НОД.

Как использовать Взаимно простые числа

Шаг 1

Введите два целых числа в поля ввода

Шаг 2

Калькулятор мгновенно определит НОД и покажет, взаимно просты ли числа

Шаг 3

Изучите разложение на простые множители и пошаговый алгоритм Евклида

Шаг 4

При НОД = 1 калькулятор также покажет коэффициенты тождества Безу

Примеры использования

15 и 28 — взаимно просты

15 = 3 × 5, 28 = 2² × 7. Общих множителей нет → НОД = 1. Тождество Безу: 15 × 2 + 28 × (−1) = 2 (здесь НОД=1: 15 × 2 + 28 × (−1) = 2, корректнее: 15 × (−13) + 28 × 7 = 1)

24 и 35 — взаимно просты

24 = 2³ × 3, 35 = 5 × 7. Ни один множитель не совпадает → НОД = 1

12 и 18 — НЕ взаимно просты

12 = 2² × 3, 18 = 2 × 3². Общие множители: 2 и 3 → НОД = 6

RSA: e=65537 и φ(n)=3233

65537 — простое число, 3233 = 53 × 61. НОД = 1, e подходит для RSA (65537 — стандартный выбор)

100 и 101 — последовательные

Любые последовательные числа взаимно просты. 100 = 2² × 5², 101 — простое. НОД = 1

Часто задаваемые вопросы

Чем взаимно простые числа отличаются от простых?

Простое число делится только на 1 и себя (2, 3, 5, 7...). Взаимно простые — это пара чисел без общих делителей, но сами числа могут быть составными. Например, 8 и 15 — оба составные, но взаимно простые (НОД = 1).

Что такое тождество Безу?

Если НОД(a, b) = d, существуют целые x и y такие, что ax + by = d. Для взаимно простых (d = 1): ax + by = 1. Это используется для нахождения обратного элемента в модулярной арифметике и RSA-шифровании.

Как быстро проверить взаимную простоту?

Алгоритм Евклида: делите большее на меньшее с остатком, затем меньшее на остаток, пока остаток не станет 0. Последний ненулевой остаток — НОД. Если он равен 1 — числа взаимно просты. Работает за доли секунды даже для очень больших чисел.

Почему в RSA ключ должен быть взаимно простым с φ(n)?

Для расшифровки нужен обратный элемент: d = e⁻¹ mod φ(n). Обратный элемент существует, только если НОД(e, φ(n)) = 1. Если это условие не выполнено — закрытый ключ невозможно вычислить, и шифрование не работает.

Может ли 0 быть взаимно простым с другим числом?

НОД(0, n) = n для любого n > 0. Поэтому 0 взаимно прост только с 1 и −1 (НОД(0, 1) = 1). Со всеми остальными числами — нет.

Сколько чисел от 1 до n взаимно просты с n?

Ровно φ(n) — функция Эйлера. Для простого p: φ(p) = p−1 (все числа кроме p). Для n = 12: φ(12) = 4 (числа 1, 5, 7, 11). Формула: φ(n) = n × ∏(1 − 1/p) для всех простых p, делящих n.

Полезная информация

🔒 Конфиденциальность Все вычисления выполняются в браузере. Введённые числа не отправляются на сервер.

🔐 Для криптографии Калькулятор показывает коэффициенты тождества Безу — используйте для нахождения обратных элементов в модулярной арифметике и проверки ключей RSA.

Комментарии (1)

Был ли полезен этот инструмент?

Руслан Авдеев (автор проекта)• 1 янв. 2024 г., 00:00

🎉 Спасибо, что используете наши инструменты! Все инструменты на ToolFox полностью бесплатны и постоянно улучшаются. 📝 Пожалуйста, оставляйте комментарии: - Если инструмент работает некорректно - Если есть идеи по улучшению - Поделитесь своим опытом использования 👍 Ставьте лайки/дизлайки - это помогает мне понять, какие инструменты нуждаются в доработке. Я обновляю сайт каждую неделю на основе вашей обратной связи. ⭐ Если вам нравится ToolFox — буду благодарен за отзыв о сайте в Яндекс.Браузере (нажмите на ⋮ → «Оценить сайт» в панели браузера). Это помогает другим людям находить наши инструменты! 😊 Также вы можете написать мне напрямую в Telegram: @avdeevrus Все доработки и улучшения по вашим пожеланиям делаю бесплатно! Благодарю за доверие и использование ToolFox! 🚀