докажите, что число 864 и 875 взаимно простые
Цель: Понять и удостовериться, что 864 и 875 взаимно простые (то есть их наибольший общий делитель равен 1).
Метод 1. Евклидов алгоритм (пошагово)
Найдём остаток от деления 875 на 864: 875 = 864 + 11, значит gcd(864, 875) = gcd(864, 11).
Теперь найдём остаток от деления 864 на 11: 864 = 11 × 78 + 6, значит gcd(11, 864) = gcd(11, 6).
Остаток от деления 11 на 6: 11 = 6 × 1 + 5, значит gcd(6, 11) = gcd(6, 5).
Остаток от деления 6 на 5: 6 = 5 × 1 + 1, значит gcd(5, 6) = gcd(5, 1).
Остаток от деления 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 взаимно простые.
