Question

Докажите что числа взаимно простые: а) 95 и 182 б) 38 и 665

Answer 1

а) 95 = 5 · 19

182 = 2 · 7 · 13

НОД (95 и 182) = 1 - наибольший общий делитель

Числа 95 и 182 взаимно простые, так как у них нет общих делителей, кроме единицы.

- - - - - - - - - - - - - - -

б) 38 = 2 · 19

665 = 5 · 7 · 19

НОД (38 и 665) = 19 - наибольший общий делитель

Числа 38 и 665 не являются взаимно простыми, так как у них есть общие делители, отличные от единицы.

Answer 2

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

а) 95 и 182:

1. Найдем НОД(95, 182) с помощью алгоритма Евклида: Начнем с деления большего числа на меньшее и продолжим деление с остатком до тех пор, пока остаток не станет равен 0.

   182 = 1 * 95 + 87 95 = 1 * 87 + 8 87 = 10 * 8 + 7 8 = 1 * 7 + 1 7 = 7 * 1 + 0

2. Когда остаток становится равным 0, мы видим, что НОД(95, 182) равен 1.

Таким образом, числа 95 и 182 взаимно просты.

б) 38 и 665:

1. Найдем НОД(38, 665) с помощью алгоритма Евклида: Начнем с деления большего числа на меньшее и продолжим деление с остатком до тех пор, пока остаток не станет равен 0.

   665 = 17 * 38 + 19 38 = 2 * 19 + 0

2. Когда остаток становится равным 0, мы видим, что НОД(38, 665) равен 19, а не 1.

Таким образом, числа 38 и 665 не взаимно просты, так как их НОД равен 19, и у них есть общий делитель, больший единицы.