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

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

Лидер AI Skill PRO

Введите расчет

Математическая формула

Взаимно простые⇔gcd⁡(a,b)=1\text{Взаимно простые} \iff \gcd\left(\text{a},\ \text{b}\right) = 1

Пример

Взаимно простые⇔gcd⁡(12,35)=1=1\text{Взаимно простые} \iff \gcd\left(12,\ 35\right) = 1 = 1
Статистика использования

Реклама

Результаты

Взаимно просты ли 12 и 35?
Да
gcd(12, 35) = 1
Наибольший общий делитель 1
Взаимно простые Да (gcd = 1)

Сообщить об ошибке на этой странице

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

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

Как пользоваться

Введите два целых числа в поля a и b и нажмите кнопку расчёта. Инструмент вычислит \(\gcd(a,\ b)\) по алгоритму Евклида. Если НОД равен 1 — числа взаимно просты; если больше — у них есть общий делитель, и взаимно простыми они не являются. Знак минус не имеет значения: взаимная простота зависит только от абсолютных величин чисел.

Как работает формула

Алгоритм Евклида раз за разом заменяет пару \((a,\ b)\) на пару \((b,\ a \bmod b)\), пока второе число не обратится в ноль. Последнее ненулевое значение и есть искомый НОД. Числа взаимно просты ровно в том случае, когда этот НОД равен 1:

$$\text{Coprime} \iff \gcd\left(\text{a},\ \text{b}\right) = 1$$

Например, у чисел 8 и 15 нет общих простых множителей, поэтому \(\gcd(8,\ 15) = 1\) и они взаимно просты — хотя ни одно из них само по себе не является простым.

Реклама
Два числа с единственным общим множителем 1, показанные как пересекающиеся множества делителей
Два числа взаимно просты, когда их единственный общий делитель — 1, поэтому \(\gcd(a,\ b) = 1\).

Разбор примера

Возьмём \(a = 12\) и \(b = 35\). Число 12 раскладывается на множители 2 и 3, а 35 — на 5 и 7. Общих простых множителей нет, значит \(\gcd(12,\ 35) = 1\). Следовательно, 12 и 35 взаимно просты. А вот 12 и 18 имеют общий делитель 6, поэтому \(\gcd(12,\ 18) = 6\) — и взаимно простыми они уже не являются.

Шаги алгоритма Евклида, сводящие два числа к НОД равному 1
Алгоритм Евклида шаг за шагом уменьшает пару, пока остаток не покажет НОД = 1.

Частые вопросы

Должны ли взаимно простые числа сами быть простыми? Нет. Взаимная простота означает лишь отсутствие общего делителя больше 1, а сами числа простыми быть не обязаны (например, 8 и 9).

Является ли единица взаимно простой с любым числом? Да. \(\gcd(1,\ n) = 1\) для любого целого \(n\), поэтому 1 взаимно проста с каждым целым числом.

Могут ли два чётных числа быть взаимно простыми? Нет. Любые два чётных числа делятся на 2, поэтому их НОД не меньше 2.

Реклама

Больше примеров взаимно простых чисел

Алгоритм Евклида многократно заменяет пару \((a,\ b)\) на \((b,\ a \bmod b)\) до тех пор, пока остаток не станет равен \(0\). Последний ненулевой остаток — это \(\gcd(a,b)\), и пара взаимно проста ровно когда это значение равно \(1\).

Пример 1 — большая пара взаимно простых чисел: gcd(1071, 1024)

  1. \(1071 \bmod 1024 = 47\)
  2. \(1024 \bmod 47 = 37\)  (поскольку \(47 \times 21 = 987\) и \(1024 - 987 = 37\))
  3. \(47 \bmod 37 = 10\)
  4. \(37 \bmod 10 = 7\)
  5. \(10 \bmod 7 = 3\)
  6. \(7 \bmod 3 = 1\)
  7. \(3 \bmod 1 = 0\) → остановка

Последний ненулевой остаток равен \(1\), поэтому \(\gcd(1071, 1024) = \) 1. Вывод: 1071 и 1024 взаимно просты (копросты) — хотя ни одно из них не является простым числом (\(1071 = 3 \times 3 \times 7 \times 17\) и \(1024 = 2^{10}\)), они не имеют общих простых делителей.

Пример 2 — пара, которая не является взаимно простой: gcd(84, 126)

  1. \(84 \bmod 126 = 84\), поэтому первый шаг просто меняет пару на \((126,\ 84)\)
  2. \(126 \bmod 84 = 42\)
  3. \(84 \bmod 42 = 0\) → остановка

Последний ненулевой остаток равен \(42\), поэтому \(\gcd(84, 126) = \) 42. Вывод: 84 и 126 НЕ являются взаимно простыми. Разложение на множители подтверждает это: \(84 = 2^2 \times 3 \times 7\) и \(126 = 2 \times 3^2 \times 7\), поэтому общая часть равна \(2 \times 3 \times 7 = 42\). Обратите внимание, что расстановка меньшего числа первым требует только одного дополнительного шага перестановки — алгоритм не требует упорядоченных входных данных.

Пример 3 — два составных числа, которые всё ещё взаимно просты: gcd(25, 54)

  1. \(54 \bmod 25 = 4\)  (поскольку \(25 \times 2 = 50\) и \(54 - 50 = 4\))
  2. \(25 \bmod 4 = 1\)  (поскольку \(4 \times 6 = 24\) и \(25 - 24 = 1\))
  3. \(4 \bmod 1 = 0\) → остановка

Последний ненулевой остаток равен \(1\), поэтому \(\gcd(25, 54) = 1\). Вывод: 25 и 54 взаимно просты. Здесь \(25 = 5^2\) и \(54 = 2 \times 3^3\); множества простых чисел \(\{5\}\) и \(\{2, 3\}\) не пересекаются. Это ключевой момент о взаимной простоте: это свойство пары, а не отдельных чисел — ни одно из чисел не должно быть простым.

Соглашения и граничные случаи

Каждый случай ниже был прогнан через этот калькулятор; в столбце результата — то, что он действительно возвращает.

СлучайВводРезультат
1 и 91, 9Да
0 и 50, 5Нет

Проверено 2026-11-08

Что означает ваш результат

Калькулятор выдаёт одно число, \(d = \gcd(a,b)\), и вывод следует из того, равно ли \(d\) единице. Каждый случай несёт определённый набор стандартных теоретико-числовых следствий.

Если gcd(a, b) = 1 — числа взаимно просты

  • Дробь \(a/b\) уже находится в сокращённом виде. Нет целого числа, большего \(1\), которое сокращалось бы в числителе и знаменателе.
  • \(a\) имеет модульное мультипликативное обратное по модулю \(b\) (и \(b\) имеет одно по модулю \(a\)): сравнение \(a \cdot x \equiv 1 \pmod b\) разрешимо с уникальным решением среди остатков \(0, 1, \ldots, b-1\). Это следует из тождества Безу, которое гарантирует целые числа \(x, y\) такие, что $$a x + b y = 1$$ Сведение этого уравнения по модулю \(b\) оставляет \(a x \equiv 1\). Для \(a = 25\), \(b = 54\): \(25 \cdot 13 - 54 \cdot 6 = 325 - 324 = 1\), поэтому обратное число \(25\) по модулю \(54\) равно \(13\).
  • Нок является простым произведением: \(\operatorname{lcm}(a,b) = a \cdot b\). Для \(25\) и \(54\), \(\operatorname{lcm} = 25 \times 54 = 1350\).
  • Китайская теорема об остатках применима к модулям \(a\) и \(b\). Любая система \(x \equiv r \pmod a\), \(x \equiv s \pmod b\) имеет решение, уникальное по модулю \(a \cdot b\) — например, уникальное по модулю \(1350\) для модулей \(25\) и \(54\).
  • Шаги по \(a\) вокруг цикла длины \(b\) посещают каждую позицию. Кратные \(0, a, 2a, 3a, \ldots\) по модулю \(b\) проходят через все \(b\) остатков перед повторением; \(a\) порождает полный цикл. Если бы gcd было \(d > 1\), ходьба касалась бы только \(b/d\) позиций, делящихся на \(d\).
  • Эквивалентно, простые разложения \(a\) и \(b\) не имеют общих простых множителей, и \(a\) учитывается функцией Эйлера \(\varphi(b)\).

Если gcd(a, b) = d > 1 — числа не являются взаимно простыми

  • Дробь \(a/b\) сокращается. Деление обеих частей на \(d\) даёт \((a/d)\,/\,(b/d)\), и эта пара взаимно проста, поэтому сокращённая дробь находится в сокращённом виде. При \(a = 84\), \(b = 126\), \(d = 42\): \(84/126 = 2/3\), и \(\gcd(2,3) = 1\).
  • Модульное обратное число \(a\) по модулю \(b\) не существует. Сравнение \(a \cdot x \equiv 1 \pmod b\) не имеет решения, поскольку каждое значение \(a x - 1\), кратное \(b\), вынуждало бы \(d \mid 1\). Более общо \(a x \equiv c \pmod b\) разрешимо только когда \(d \mid c\), и тогда оно имеет ровно \(d\) решений по модулю \(b\).
  • Нок меньше произведения: \(\operatorname{lcm}(a,b) = \dfrac{a \cdot b}{d}\). Для \(84\) и \(126\): \(\operatorname{lcm} = \dfrac{84 \times 126}{42} = \dfrac{10584}{42} = 252\).
  • Тождество Безу всё ещё справедливо, но в форме \(a x + b y = d\) — наименьшее положительное значение \(a x + b y\) может быть \(d\), никогда не \(1\). Китайская теорема об остатках в своей основной форме не применима к модулям \(a\) и \(b\).

Граничные случаи

  • \(\gcd(1, n) = 1\) для каждого целого числа \(n\), поэтому \(1\) взаимно просто со всем, включая \(0\) и саму себя: \(\gcd(1,1) = 1\).
  • \(\gcd(0, n) = |n|\), поскольку каждое целое число делит \(0\). Поэтому \(0\) взаимно просто только с \(1\) и \(-1\).
  • \(\gcd(0, 0)\) не имеет наибольшего общего делителя — каждое целое число делит \(0\), поэтому множество общих делителей неограничено. По соглашению оно определяется как \(0\), и пара \((0,0)\) не является взаимно простой.
  • Знак не имеет значения: \(\gcd(a,b) = \gcd(|a|, |b|)\), поэтому \(\gcd(-25, 54) = 1\) так же как \(\gcd(25, 54) = 1\).
  • Число взаимно просто с собой только когда \(|a| = 1\), поскольку \(\gcd(a,a) = |a|\).
Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика