Нод(35;24)

Задача: нод(35;24) — найдём наибольший общий делитель чисел 35 и 24. Пошаговое решение (алгоритм Евклида): 1) gcd(35, 24) = gcd(24, 35 mod 24) = gcd(24, 11) (потому что 35 mod 24 = 11) 2) gcd(24, 11) = gcd(11, 24 mod 11) = gcd(11, 2) (24 mod 11 = 2) 3) gcd(11, 2) = gcd(2, 11 mod 2) = gcd(2, 1) (11 mod 2 = 1) 4) gcd(2, 1) = gcd(1, 2 mod 1) = gcd(1, 0) (2 mod 1 = 0) Завершаем: gcd(1, 0) = 1. Значит, наибольший общий делитель 35 и 24 равен 1. Дополнительно: почему gcd = 1 - Признаки разложения на простые множители: 35 = 5 · 7, 24 = 2^3 · 3. Общих простых факторов нет, значит gcd = 1. - Также можно записать решение в виде линейной комбинации: существует целые x, y такие, что 35x + 24y = 1. Пример через разложение назад по шагам Евклида: 11 = 35 − 24 2 = 24 − 2·11 1 = 11 − 5·2 Подставляем последовательно: 1 = 11 − 5(24 − 2·11) = 11·11 − 5·24 = (35 − 24)·11 − 5·24 = 11·35 − 16·24 Таким образом, 35·11 + 24(−16) = 1, что подтверждает gcd = 1.