Question

Найдите наибольший общий делитель : а) НОД (15; 25) б) НОД (48; 32) в) НОД (128; 96) г) НОД (1010; 101)

Answer 1

а)15 = 3 * 5

25 = 5 * 5

НОД (15; 25) = 5

б)48 = 2 * 2 * 2 * 2 * 3

32 = 2 * 2 * 2 * 2 * 2

НОД (48; 32) = 2 * 2 * 2 * 2 = 16

в)128 = 2 * 2 * 2 * 2 * 2 * 2 * 2

96 = 2 * 2 * 2 * 2 * 2 * 3

НОД (128; 96) = 2 * 2 * 2 * 2 * 2 = 32

г) 1010 = 2 * 5 * 101

101 = 101

НОД (1010; 101) = 101

Answer 2

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

а) НОД(15; 25): 25 = 15 * 1 + 10 Теперь заменяем 25 на 15 и 15 на 10: 15 = 10 * 1 + 5 Теперь заменяем 15 на 10 и 10 на 5: 10 = 5 * 2 + 0

Как видно, когда мы получили остаток 0, следующим шагом будет делить на 5. Таким образом, НОД(15; 25) = 5.

б) НОД(48; 32): 48 = 32 * 1 + 16 Теперь заменяем 48 на 32 и 32 на 16: 32 = 16 * 2 + 0

Как видно, когда мы получили остаток 0, следующим шагом будет делить на 16. Таким образом, НОД(48; 32) = 16.

в) НОД(128; 96): 128 = 96 * 1 + 32 Теперь заменяем 128 на 96 и 96 на 32: 96 = 32 * 3 + 0

Как видно, когда мы получили остаток 0, следующим шагом будет делить на 32. Таким образом, НОД(128; 96) = 32.

г) НОД(1010; 101): 1010 = 101 * 9 + 19 Теперь заменяем 1010 на 101 и 101 на 19: 101 = 19 * 5 + 16 Заменяем 101 на 19 и 19 на 16: 19 = 16 * 1 + 3 Заменяем 19 на 16 и 16 на 3: 16 = 3 * 5 + 1 Заменяем 16 на 3 и 3 на 1: 3 = 1 * 3 + 0

Как видно, когда мы получили остаток 0, следующим шагом будет делить на 1. Таким образом, НОД(1010; 101) = 1.