Керування
Обчислення
НСД — добуток спільних простих множників (у найменших степенях); НСК — добуток усіх множників (у найбільших степенях); НСД(a, b) · НСК(a, b) = a · b.
Завдання
Чому так?
Ознаки подільності. Число ділиться на 2, якщо його остання цифра парна (0, 2, 4, 6, 8); на 5 — якщо закінчується на 0 або 5; на 10 — якщо закінчується на 0. Це тому, що 10 ділиться і на 2, і на 5, тож усе, крім останньої цифри, вже ділиться. Число ділиться на 3 (на 9), якщо сума його цифр ділиться на 3 (на 9): 10 = 9 + 1, 100 = 99 + 1, тому кожна цифра дає ту саму остачу, що й сама. Приклад: 4 572 → 4 + 5 + 7 + 2 = 18, отже 4 572 ділиться і на 3, і на 9.
Прості й складені числа. Просте число має рівно два дільники: 1 і саме себе (2, 3, 5, 7, 11, …). Складене має більше двох дільників. Число 1 — ні просте, ні складене. Кожне складене число розкладається на прості множники, і до порядку множників цей розклад єдиний: 84 = 2² · 3 · 7.
Решето Ератосфена. Беремо найменше незакреслене число — воно просте — і закреслюємо всі його кратні. Для чисел до 100 досить пройти 2, 3, 5 і 7: якщо складене число n ≤ 100, у нього є простий дільник, не більший за √100 = 10. Усе, що лишилося незакресленим, — прості числа (їх 25).
НСД і НСК через розклад. 84 = 2² · 3 · 7, 90 = 2 · 3² · 5. Спільні множники 2 і 3, тому НСД(84, 90) = 2 · 3 = 6. НСК бере кожен простий множник у найбільшому степені: 2² · 3² · 5 · 7 = 1 260.
Алгоритм Евкліда. Спільний дільник чисел a і b ділить і остачу від ділення a на b, тому НСД(a, b) = НСД(b, r). Ділимо, доки остача не стане 0: 90 = 84 · 1 + 6, 84 = 6 · 14 + 0 → НСД = 6.
Зв'язок НСД і НСК. НСД бере кожен спільний множник у меншому степені, а НСК — у більшому; разом вони містять усі множники обох чисел, тому НСД(a, b) · НСК(a, b) = a · b. Перевірка: 6 · 1 260 = 7 560 = 84 · 90. Звідси зручно: НСК(a, b) = a · b : НСД(a, b).