Question

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

Answer 1

Два целых числа называются взаимно простыми если они не имеют никаких общих делителей, кроме 1.

864 | 2                 875 | 5

432 | 2                 155 | 5

216 | 2                   35 | 5

108 | 2                     7 | 7

  54 | 2                     1 | 1

  27 | 3

   9 | 3

    3|3

    1|1

Общих делителей у чисел 864 и 875, кроме 1, нет, значит эти числа взаимно простые.

Answer 2

Два числа считаются взаимно простыми, если их наибольший общий делитель (НОД) равен 1. Давайте проверим, являются ли числа 864 и 875 взаимно простыми, найдя их НОД.

1. Первый способ: использование алгоритма Евклида.

   • Найдем НОД(864, 875) с помощью алгоритма Евклида:

     • Делим 875 на 864: 875 = 864 * 1 + 11.
     • Делим 864 на 11: 864 = 11 * 78 + 6.
     • Делим 11 на 6: 11 = 6 * 1 + 5.
     • Делим 6 на 5: 6 = 5 * 1 + 1.
     • Делим 5 на 1: 5 = 1 * 5 + 0.

   • Последний ненулевой остаток равен 1, поэтому НОД(864, 875) = 1.

   Поскольку НОД(864, 875) = 1, числа 864 и 875 являются взаимно простыми.

2. Второй способ: факторизация чисел.

   • Факторизуем число 864: 864 = 2^5 * 3^3.

   • Факторизуем число 875: 875 = 5^3 * 7.

   • Заметим, что у них нет общих простых множителей (кроме 1), поэтому их НОД равен 1.

   Используя как алгоритм Евклида, так и факторизацию, мы пришли к выводу, что числа 864 и 875 взаимно простые.