Як знайти НСД: блискавичні методи з прикладами

Два числа маячать перед очима: 48 і 18. Найбільше число, яке ділить обидва без остачі, — шість. Цей трюк ховається в алгоритмі Евкліда, простому ланцюжку ділення з остачею, що працює за секунди. НСД(48, 18) = 6, і ось чому: 48 ÷ 18 = 2 з остачею 12, потім 18 ÷ 12 = 1 з остачею 6, 12 ÷ 6 = 2 без остачі. Готово! А для новачків це як гра в доміно — падають числа, доки не дійдеш до мети.

Навіть з трьома числами, скажімо 12, 18 і 30, спочатку береш НСД(12, 18) = 6, потім НСД(6, 30) = 6. Швидко й надійно. Цей підхід перевершує нудний перелік усіх дільників, бо масштабується на будь-які величини, від шкільних задачок до гігантських криптографічних ключів.

Найбільший спільний дільник, або НСД, — це той “король дільників”, який ховається в кожній парі чисел і відкриває двері до спрощень дробів чи обчислень кратних. Розберемося, чому Евклідів метод кращий за все інше, і як його освоїти за хвилини.

Що ховається за поняттям НСД і чому воно всюди

Уявіть числа як фортеці з цеглинок — простих множників. НСД — спільна стіна, яку можна зруйнувати з обох боків без пилу. Для 100 і 150 це 50: 100 = 2² × 5², 150 = 2 × 3 × 5², спільне — 2 × 5². Без нього дроби на кшталт 100/150 не спростяться до соковитих 2/3.

Ця магія народилася ще 2300 років тому в “Началах” Евкліда, давньогрецького генія з Александрії. Алгоритм з’явився близько 300 року до н.е. в книгах VII і X, де Евклід показав його для чисел і навіть геометричних відрізків (uk.wikipedia.org). Досі це найстаріший алгоритм, що вижив у комп’ютерах — від Python до суперкомп’ютерів.

Сьогодні НСД — не просто шкільна тема. Він спрощує дроби в кулінарії (подвійте рецепт на 3/4 порції), синхронізує цикли в графіці (найменше спільне кратне йде слідом) і блокує хакерів у RSA-криптографії, де НСД=1 гарантує безпеку ключів.

Перший метод: розклад на прості множники як фундамент

Почніть з малого — розкладіть числа на “атоми” математики. Це повільно для гігантів, але ідеально для новачків, бо видно все на долоні. Візьміть 36 і 60: 36 = 2² × 3², 60 = 2² × 3 × 5. Спільні — 2² × 3 = 12. НСД=12.

Ось покроковий план, щоб не заплутатися:

• Оберіть найменше число й перевірте подільність на 2, 3, 5 — від простих до більших.
• Запишіть степені: для 72 = 2³ × 3², не забудьте куби!
• Випишіть спільні множники з найменшими степенями: для 72 і 48 (2⁴ × 3) — 2³ × 3 = 24.
• Помножте: результат — ваш НСД.

Цей спосіб сяє в задачах з малими числами, бо малюнок розкладу запам’ятовується. Але для 10⁶ і 10⁹? Забудьте — Евклід швидший у тисячі разів.

Алгоритм Евкліда: король швидкості з математичним доказом

Евклід не просто вигадав — довів: НСД(a, b) = НСД(b, a mod b). Це як рекурсивний танець чисел, що звужується до нуля. Приклад з 1008 і 576: 1008 ÷ 576 = 1, остача 432; 576 ÷ 432 = 1, остача 144; 432 ÷ 144 = 3, остача 0. НСД=144.

Таблиця кроків для наочності:

Останній ненульовий остача — перемога. Джерела даних: mathema.me, uk.wikipedia.org. Цей метод логарифмічно швидкий — O(log min(a,b)) кроків, ідеал для комп’ютерів.

1. Покладіть a > b, якщо ні — поміняйте.
2. Обчисліть остачу r = a % b.
3. Повторіть з b і r, доки r ≠ 0.
4. Коли b=0, a — НСД.

З останньою нульовою остачею числа танцюють до фінішу. Спробуйте з 123456 і 789: за 10 кроків отримаєте 3. Чарівно!

НСД для трьох чи більше чисел: послідовний наступ

Більше чисел — не проблема. Беріть по черзі: НСД(a, b, c) = НСД( НСД(a,b), c ). Приклад: 24, 36, 48. Спочатку НСД(24,36)=12, потім НСД(12,48)=12.

Інший кейс — 105, 231, 385. НСД(105,231)=21 (105=3×5×7, 231=3×7×11), НСД(21,385)=7 (385=5×7×11). Результат 7.

• Розрахуйте пари: НСД перших двох.
• Додайте третє: НСД(попереднього, наступне).
• Повторюйте для купи чисел — алгоритм масштабується.
• Перевірте: розділіть кожне на НСД без остачі.

Для 16,20,28: НСД(16,20)=4, НСД(4,28)=4. Простіше простого, і це формула.co.ua підтверджує прикладами.

Двійковий алгоритм: для програмістів і бітових магів

Звичайний Евклід ділить — повільно на комп’ютерах без апаратного mod. Двійковий варіант (Стайна, 1961) використовує біти: зсуви замість ділення, вдвічі швидше на великих числах.

Правила блискавичні: якщо обидва парні, НСД парний — поділіть на 2 і множте зсув. Один парний — приберіть 2-ки з нього. Обидва непарні — відніміть і зсуньте.

Приклад коду Python — скопіюйте й запустіть:

def binary_gcd(a, b):
    if a == 0: return b
    if b == 0: return a
    shift = 0
    while ((a | b) & 1) == 0:
        a >>= 1; b >>= 1; shift += 1
    while (a & 1) == 0: a >>= 1
    while b:
        while (b & 1) == 0: b >>= 1
        if a > b: a, b = b, a
        b -= a
    return a << shift

Тест: binary_gcd(48,18) видасть 6. Економить цикли в крипті, де числа — мільйони бітів.

Де НСД оживає: від кухні до кібербезпеки

Спростіть 36/54: НСД=18, виходить 2/3 — рецепт на двох вистачить. НСК(a,b)=a*b/НСД — для розкладу 12 плиток на 4 і 6 осіб: НСК=12.

У програмуванні — хеш-таблиці, графіки. У криптографії RSA: генерують p,q прості, n=pq, обирають e з НСД(e, (p-1)(q-1))=1. Розширений Евклід знаходить d для розшифровки. Без НСД — ніякої безпеки в банках чи чатах.

Статистика вражає: у Linux ядрі алгоритм Евкліда — тисячі викликів за секунду для синхронізації.

Порівняння методів: оберіть свій

Який метод для вас? Таблиця розставить крапки:

Для школи — множники з малюнками. Для коду — двійковий. Переходьте між ними залежно від задачі, і ніякі числа не встоять.

Експериментуйте з калькуляторами на onlinemschool.com, але руками — найкращий тренінг. А тепер візьміть свої числа й полічіть — відчуйте драйв відкриття!