Перейти к содержимому
Все инструментыЛичный кабинет
🔢

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

Проверка взаимной простоты двух натуральных чисел до 1 000 000 000 000: разложение на множители, НОД, общие делители и коэффициенты Безу

Открывали 4 608 раз

Инструмент справился с вашей задачей?

Одно нажатие, без регистрации. По ответам мы решаем, какие инструменты дорабатывать первыми.

Уже ответили: 15 человек

Этот инструмент ещё ждёт первого комментария

Нашли приём, остался вопрос или чего-то не хватило — напишите, пригодится следующим. Почту и пароль указывать не нужно · публикуем после проверки, обычно за 1–2 дня · если вам ответят, ответ появится здесь же

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

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

  • Проверка взаимной простоты двух натуральных чисел до 1 000 000 000 000
  • Нахождение НОД через общие простые множители — с подробным решением
  • Разложение обоих чисел на простые множители
  • Нахождение коэффициентов тождества Безу (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.

      1

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

      2

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

      3

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

      4

      Калькулятор показал тождество Безу: 17 × (−367) + 3120 × 2 = 1. Коэффициент при 17 отрицательный — прибавил 3120: −367 + 3120 = 2753 → закрытый ключ d = 2753

      ✅

      Ключ подходит: 17 × 2753 = 46 801 = 15 × 3120 + 1, то есть d = 2753 — обратный к e по модулю 3120. Обратный элемент дал коэффициент Безу, расширенный алгоритм Евклида вручную прогонять не пришлось.

      🧠

      Знаете ли вы?

      🔐

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

      📊

      Доля взаимно простых пар среди пар чисел от 1 до N с ростом N стремится к 6/π² ≈ 60,8%. Число π²/6 — сумма ряда 1 + 1/4 + 1/9 + …, которую нашёл Эйлер, решая Базельскую задачу

      🔢

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

      🧮

      Алгоритм Евклида делает O(log n) делений с остатком: для чисел до миллиарда — не больше 42. Худший случай — соседние числа Фибоначчи, например 701 408 733 и 433 494 437

      🎵

      Отношение частот любого интервала записывают несократимой дробью — октава 2:1, квинта 3:2, но и диссонирующая малая секунда 16:15: созвучие зависит от величины чисел, а не от взаимной простоты

      ⚙️

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

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

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

      Важно знать

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

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

      1

      Шаг 1

      Введите два натуральных числа до 1 000 000 000 000 в поля «Первое число» и «Второе число» или нажмите один из примеров под полями

      2

      Шаг 2

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

      3

      Шаг 3

      Изучите подробное решение: разложение на простые множители, общие множители, НОД и все общие делители пары

      4

      Шаг 4

      Калькулятор также покажет коэффициенты тождества Безу: a × x + b × y = НОД — при любом НОД, не только при НОД = 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 = 65 537 и φ(n) = 1 020 096

      Учебный ключ: n = 1009 × 1013 = 1 022 117, φ(n) = 1008 × 1012 = 1 020 096 = 2⁶ × 3² × 7 × 11 × 23. 65 537 — простое число, на него φ(n) не делится, поэтому НОД = 1 и e подходит для RSA (65 537 — стандартный выбор)

      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.
      Сколько чисел от 1 до n взаимно просты с n?
      Ровно φ(n) — функция Эйлера. Для простого p: φ(p) = p−1 (все числа кроме p). Для n = 12: φ(12) = 4 (числа 1, 5, 7, 11). Формула: φ(n) = n × ∏(1 − 1/p) для всех простых p, делящих n.
      Все ли простые числа взаимно просты между собой?
      Два разных простых числа всегда взаимно просты: у каждого ровно два делителя — 1 и оно само, поэтому общий делитель только 1. Например, НОД(7, 13) = 1. Но два одинаковых простых числа не взаимно просты: НОД(5, 5) = 5.
      Как связаны взаимно простые числа и несократимые дроби?
      Дробь несократима тогда и только тогда, когда её числитель и знаменатель взаимно просты. Например, 15/28 несократима, ведь НОД(15, 28) = 1. А 12/18 сокращается до 2/3, потому что НОД(12, 18) = 6 — числа не взаимно просты.

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

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

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

      Смежные инструменты теории чисел

      Если вы проверяли взаимную простоту, эти калькуляторы продолжают тему — НОД и НОК, функция Эйлера, разложение на множители и делители числа.

      Калькулятор НОД и НОК
      Наибольший общий делитель и наименьшее общее кратное двух чисел
      Функция Эйлера φ(n)
      Сколько чисел от 1 до n взаимно просты с n
      Разложение на простые множители
      Каноническое разложение любого натурального числа
      Делители числа
      Все делители числа и их количество
      Проверка числа на простоту
      Простое число или составное — мгновенная проверка
      Таблица простых чисел
      Список простых чисел до 100, 1000, 10000

      Комментарии

      Этот инструмент ещё ждёт первого комментария

      Почту и пароль указывать не нужно · публикуем после проверки, обычно за 1–2 дня · если вам ответят, ответ появится здесь же

      • Руслан АвдеевОт автора проекта
        Все инструменты на ToolFox бесплатны, и я их дорабатываю сам. Напишите, если инструмент считает неверно, чего-то не хватает или что-то стоит поправить, — по таким комментариям я и решаю, чем заняться дальше.

      Комментарии — мнения посетителей, прошедшие проверку по правилам сайта.