Взаимно простые числа
Проверка взаимной простоты чисел: разложение на множители, НОД и коэффициенты Безу
Калькулятор взаимно простых чисел — проверка и нахождение
Онлайн калькулятор для проверки взаимной простоты двух чисел. Инструмент находит НОД через алгоритм Евклида, раскладывает числа на простые множители и определяет, являются ли они взаимно простыми (НОД = 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 × (−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
Часто задаваемые вопросы
Чем взаимно простые числа отличаются от простых?
Что такое тождество Безу?
Как быстро проверить взаимную простоту?
Почему в RSA ключ должен быть взаимно простым с φ(n)?
Может ли 0 быть взаимно простым с другим числом?
Сколько чисел от 1 до n взаимно просты с n?
Все ли простые числа взаимно просты между собой?
Как связаны взаимно простые числа и несократимые дроби?
Полезная информация
🔒 Конфиденциальность Все вычисления выполняются в браузере. Введённые числа не отправляются на сервер.
🔐 Для криптографии Калькулятор показывает коэффициенты тождества Безу — используйте для нахождения обратных элементов в модулярной арифметике и проверки ключей RSA.
Смежные инструменты теории чисел
Если вы проверяли взаимную простоту, эти калькуляторы продолжают тему — НОД и НОК, функция Эйлера, разложение на множители и делители числа.