Question

Докажите, что числа 945 и 208 - взаимно простые ​

Answer 1

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

Раскладываем на простые множители

1) 945 | 5

   189 | 3

    63 | 3

     21 | 3

      7  | 7

       1  | 1

945=5*3³*7*1

2) 208 | 2

    104 | 2

     52  | 2

     26  | 2

      13  | 13

         1 | 1

208=2⁴*13*1

Как видим, общий множитель у этих двух чисел только 1.

То есть НОД(945, 208)=1

Значит, 945 и 208 - взаимно простые числа - ч.т.д.

Answer 2

Для доказательства того, что числа 945 и 208 являются взаимно простыми, мы можем воспользоваться алгоритмом нахождения наибольшего общего делителя (НОД) двух чисел. Если НОД чисел равен 1, то они взаимно простые.

Давайте найдем НОД чисел 945 и 208, используя алгоритм Евклида:

1. Делаем первое деление: 945 / 208 = 4 (с остатком 169).
2. Делаем второе деление: 208 / 169 = 1 (с остатком 39).
3. Делаем третье деление: 169 / 39 = 4 (с остатком 13).
4. Делаем четвертое деление: 39 / 13 = 3 (с остатком 0).

Как только остаток становится равным 0, мы останавливаемся. НОД чисел 945 и 208 равен последнему ненулевому остатку, который равен 13.

Таким образом, НОД(945, 208) = 13.

Поскольку НОД чисел 945 и 208 не равен 1, это означает, что числа 945 и 208 не взаимно просты.