НСД і НСК: дільники, кратні та алгоритм Евкліда
Дільники й кратні
Просте число має рівно два дільники: 1 і саме себе (2, 3, 5, 7, 11, …). Складене має більше двох. Число 1 не є ні простим, ні складеним.
НСД і НСК
Якщо розкласти числа на прості множники, то НСД — це добуток спільних множників (у найменших степенях), а НСК — добуток усіх множників (у найбільших степенях). Числа, НСД яких дорівнює 1, називають взаємно простими.
Алгоритм Евкліда
Щоб знайти НСД, ділять більше число на менше з остачею, потім менше — на остачу, і так до нульової остачі. Остання ненульова остача — НСД.
Приклади
Показати розв’язок
, .
НСД , НСК . Перевірка: .
За Евклідом: , , тож НСД .
Показати розв’язок
НСД(84; 126) = 42. Тоді .