Что такое калькулятор взаимно простых чисел?
Два целых числа называются взаимно простыми (или взаимно простыми между собой), если единственное натуральное число, на которое делятся оба, — это единица. Иными словами, их наибольший общий делитель (НОД) равен ровно 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\) и они взаимно просты — хотя ни одно из них само по себе не является простым.
Разбор примера
Возьмём \(a = 12\) и \(b = 35\). Число 12 раскладывается на множители 2 и 3, а 35 — на 5 и 7. Общих простых множителей нет, значит \(\gcd(12,\ 35) = 1\). Следовательно, 12 и 35 взаимно просты. А вот 12 и 18 имеют общий делитель 6, поэтому \(\gcd(12,\ 18) = 6\) — и взаимно простыми они уже не являются.
Частые вопросы
Должны ли взаимно простые числа сами быть простыми? Нет. Взаимная простота означает лишь отсутствие общего делителя больше 1, а сами числа простыми быть не обязаны (например, 8 и 9).
Является ли единица взаимно простой с любым числом? Да. \(\gcd(1,\ n) = 1\) для любого целого \(n\), поэтому 1 взаимно проста с каждым целым числом.
Могут ли два чётных числа быть взаимно простыми? Нет. Любые два чётных числа делятся на 2, поэтому их НОД не меньше 2.
