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

Важное правило: числа могут быть взаимно простыми, но при этом не являться простыми. То есть оба числа могут иметь иные делители, кроме 1. Главное — чтобы эти делители не совпадали. Так, числа 8 и 15 — не простые: 8 делится на 2, а 15 — на 5. Тем не менее, они взаимно просты, так как общий делитель у них только один — единица.

Если у двух чисел есть иные общие делители, назвать их взаимно простыми невозможно. Простой пример — числа 6 и 9. У них есть общий делитель — 3.

Есть разные способы доказать взаимную простоту двух чисел. Самый распространённый — алгоритм Евклида. С помощью него ищут наибольший общий делитель (НОД) для двух чисел. Если представить два числа как a и b, для поиска НОД следует использовать формулу НОД(a, b) = НОД(b, a mod b). Mod — операция взятия остатка от деления. Например, если мы поделим число 21 на 8, остатком от деления будет 5.

Допустим, нам нужно проверить взаимную простоту чисел 21 и 8. Нужно выполнить следующие шаги:

1. a = 21, b = 8
2. НОД(21, 8) = НОД(8, 21 mod 8) = НОД(8, 5)
3. НОД(8, 5) = НОД(5, 8 mod 5) = НОД(5, 3)
4. НОД(5, 3) = НОД(3, 5 mod 3) = НОД(3, 2)
5. НОД(3, 2) = НОД(2, 3 mod 2) = НОД(2, 1)
6. НОД(2, 1) = НОД(1, 2 mod 1) = НОД(1, 0)

Проверь знания по предметуМатематика

НОД(21, 8) = 1. Это означает, что числа 21 и 8 являются взаимно простыми.