Докажите, что число 864 и 875 взаимно простые

Цель: Понять и удостовериться, что 864 и 875 взаимно простые (то есть их наибольший общий делитель равен 1). Метод 1. Евклидов алгоритм (пошагово) 1) Найдём остаток от деления 875 на 864: 875 = 864 + 11, значит gcd(864, 875) = gcd(864, 11). 2) Теперь найдём остаток от деления 864 на 11: 864 = 11 × 78 + 6, значит gcd(11, 864) = gcd(11, 6). 3) Остаток от деления 11 на 6: 11 = 6 × 1 + 5, значит gcd(6, 11) = gcd(6, 5). 4) Остаток от деления 6 на 5: 6 = 5 × 1 + 1, значит gcd(5, 6) = gcd(5, 1). 5) Остаток от деления 5 на 1: 5 = 1 × 5 + 0, значит gcd(1, 0) = 1. Вывод: gcd(864, 875) = 1. Значит числа 864 и 875 взаимно простые. Метод 2. Разложение на простые множители (для проверки) - 864 = 2^5 × 3^3 (то есть множители 2 и 3). - 875 = 5^3 × 7 (то есть множители 5 и 7). У чисел нет общих простых делителей, поэтому gcd(864, 875) = 1. Дополнительное пояснение (интуитивно) Разность чисел: 875 − 864 = 11. Любой общий делитель d должен делить и разность 11, и оба числа. Значит d делит 11. Единственные делители 11 — 1 и 11. Но 11 не делит ни 864, ни 875, следовательно d может быть только 1. Значит gcd = 1. Итог: 864 и 875 взаимно простые.