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

Два целых числа взаимно просты, когда их наибольший общий делитель равен ровно единице. Сами числа не обязаны быть простыми. Например, 14 и 25 — составные: у 14 есть множители 2 и 7, а у 25 — множитель 5, но общих положительных делителей, кроме 1, нет. Напротив, 18 и 24 имеют общие делители 2, 3 и 6, поэтому их наибольший общий делитель равен 6 и они не взаимно просты. Калькулятор находит наибольший общий делитель алгоритмом Евклида. Начиная с абсолютных значений обоих целых чисел, он многократно заменяет текущую пару делителем и остатком. Для 18 и 24 остатки в конце концов становятся равны 6, затем 0. Последний ненулевой остаток и есть наибольший общий делитель. Алгоритм эффективен даже для больших целых чисел, поскольку каждый остаток быстро уменьшает размер следующего вычисления. Взаимная простота — отношение между числами, а не свойство одного числа. Число 8 взаимно просто с 15, поскольку их НОД равен 1, но не с 12, так как у них есть общий делитель 4. Последовательные целые числа всегда взаимно просты: любой общий делитель n и n плюс 1 должен делить и их разность, равную 1. Аналогично любое целое число взаимно просто с 1. Взаимно простые числа лежат в основе сокращения дробей. Дробь несократима тогда и только тогда, когда её числитель и знаменатель взаимно просты. Они также встречаются в модульной арифметике, функции Эйлера, циклических структурах, передаточных отношениях шестерён и криптографии с открытым ключом. В математике типа RSA выбор значений с НОД, равным единице, гарантирует существование обратного элемента по модулю. Отрицательные числа допустимы, поскольку знак не меняет общие положительные делители; для НОД калькулятор использует абсолютные значения. С нулём нужна осторожность. НОД нуля и ненулевого целого числа равен модулю этого числа, поэтому ноль взаимно прост только с 1 или минус 1. Пара ноль и ноль отклоняется: в используемом здесь соглашении её наибольший общий делитель не определён. Вводите целые числа, так как взаимная простота и делимость — дискретные понятия теории чисел.