Калькулятор НСД

Q: Чому дорівнює НСД числа й 0?

Будь-яке ціле число ділить 0, тому gcd(a, 0) = |a|. НСД чисел 0 і 0 не визначений.

Про калькулятор НСД

Найбільший спільний дільник набору цілих чисел — це найбільше натуральне число, на яке кожне з них ділиться без остачі. Він потрібен, щоб скорочувати дроби, виносити спільний множник за дужки та ділити предмети на рівні групи.

Калькулятор розкладає кожне число на прості множники й паралельно виконує алгоритм Евкліда, щоб ви могли порівняти наочний спосіб із найшвидшим.

Що таке найбільший спільний дільник?

Дільник цілого числа ділить його без остачі: дільники 12 — це 1, 2, 3, 4, 6 і 12. Спільний дільник кількох чисел ділить їх усі, а найбільший спільний дільник — найбільший із них. Дільники 18 — це 1, 2, 3, 6, 9 і 18, тому спільні дільники 12 і 18 — це 1, 2, 3 і 6, а НСД дорівнює 6.

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

Як користуватися калькулятором НСД

Введіть від двох до десяти цілих чисел через кому або пробіл.
Натисніть «Знайти НСД».
Перегляньте розкладання кожного числа на прості множники, спільні прості множники та ділення алгоритму Евкліда.

Формули

Алгоритм Евкліда

\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a

Через розкладання на прості множники

\gcd = \prod p^{\min(e_1, e_2, \ldots)}

Кожен спільний простий множник береться в найменшому степені.

Зв'язок із НСК

\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |ab|

Розв'язаний приклад: 48, 180

У розв'язаному прикладі шукається НСД чисел 48 і 180. Розкладання на прості множники дає $48 = 2^4 \times 3$ і $180 = 2^2 \times 3^2 \times 5$ . Алгоритм Евкліда ділить 180 на 48 (остача 36), потім 48 на 36 (остача 12), потім 36 на 12 (остача 0), отже, НСД дорівнює 12. Спільні прості множники в найменших степенях, $2^2 \times 3 = 12$ , підтверджують це, а перевірка показує, що 48 і 180, поділені на 12, дають 4 і 15.

Розв'язок нижче побудовано тим самим обчислювальним рушієм, що й калькулятор вище.

Відповідь

12

Як ми зрозуміли вашу задачу

Знаходимо найбільший спільний дільник (НСД) чисел.

Покроковий розв'язок

Розкладання кожного числа на прості множники
$48 = 2^{4} \times 3,\quad 180 = 2^{2} \times 3^{2} \times 5$
Алгоритм Евкліда для GCF(48, 180)
180 = 3 × 48 + 36; 48 = 1 × 36 + 12; 36 = 3 × 12 + 0
$180 = 3 \times 48 + 36 \\ 48 = 1 \times 36 + 12 \\ 36 = 3 \times 12 + 0$
Остання ненульова остача і є НСД
$\gcd(48, 180) = 12$
Перевіряємо за спільними простими множниками
Перемножуємо прості множники, спільні для всіх чисел, кожен у найменшому степені.
$2^{2} \times 3 = 12$

Використані формули

Алгоритм Евкліда
$\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a$

12 — найбільше ціле число, на яке ділиться без остачі кожне з чисел.

Перевірка

48 ÷ 12 = 4
180 ÷ 12 = 15

Докладне пояснення

Чому працює алгоритм Евкліда

Будь-яке число, що ділить $a$ і $b$ , ділить і $a - b$ , а отже, і остачу від ділення $a$ на $b$ . Тому пара $(a, b)$ і пара $(b, a \bmod b)$ мають ті самі спільні дільники. Кожен крок зменшує числа, і коли остача стає рівною 0, число, що залишилося, ділить саме себе й 0, тобто є найбільшим спільним дільником. Навіть для дуже великих чисел алгоритму потрібно лише кілька ділень, тому його використовують у комп'ютерній арифметиці та криптографії.

Де потрібен НСД

Якщо поділити чисельник і знаменник на їхній НСД, дріб одразу стає нескоротним: $\frac{48}{180} = \frac{4}{15}$ . В алгебрі спершу виносять за дужки НСД коефіцієнтів, як у $12x + 18 = 6(2x + 3)$ . У життєвих задачах він відповідає на запитання про найбільшу кількість однакових груп: 24 олівці, 36 гумок і 60 наліпок можна розкласти не більш ніж у 12 однакових наборів, бо $\gcd(24, 36, 60) = 12$ .

Розкладання на множники чи алгоритм Евкліда

Розкладання на прості множники показує структуру: видно, які саме прості множники мають числа і чому відповідь саме така. Це допомагає під час вивчення теми або коли потрібне ще й НСК. Слабке місце — великі числа розкладати довго. Алгоритм Евкліда нічого не розкладає: він лише ділить і запам'ятовує остачі, тому залишається швидким навіть для чисел із десятків цифр. Калькулятор показує обидва способи, щоб один підтверджував інший.

Типові помилки

Перемножувати всі прості множники, що трапляються, а не лише спільні.
Брати спільний простий множник у найбільшому степені; для НСД потрібен найменший.
Вважати, що НСД не існує, якщо числа взаємно прості; у цьому разі НСД дорівнює 1.
Зупиняти алгоритм Евкліда на крок раніше й записувати останню неповну частку замість останньої ненульової остачі.

Поради

Якщо одне число ділить усі інші, воно і є НСД.
НСД двох сусідніх цілих чисел завжди дорівнює 1.
Скорочуйте дріб на НСД чисельника й знаменника за один крок.
Перевірте відповідь, поділивши на неї кожне число: частки не повинні мати спільних дільників, крім 1.
Для трьох і більше чисел спершу знайдіть НСД двох, потім об'єднайте результат із наступним числом.

Поширені запитання

Що таке найбільший спільний дільник?

Це найбільше натуральне число, на яке всі числа набору діляться без остачі. Для 48 і 180 він дорівнює 12.

НСД, GCD, GCF, HCF — це одне й те саме?

Так. Українською кажуть НСД, а в англомовних джерелах те саме число позначають GCD, GCF або HCF.

Як працює алгоритм Евкліда?

Поділіть більше число на менше й запишіть остачу. Замініть пару на (менше число, остача) і повторюйте, доки остача не стане рівною 0; останній ненульовий дільник і є НСД.

Чому дорівнює НСД чисел без спільних дільників?

Він дорівнює 1. Такі числа називають взаємно простими, наприклад 8 і 15.

Чи можна знайти НСД від'ємних чисел?

Так. Подільність не залежить від знака: НСД знаходять за модулями чисел, і він завжди додатний.

Чому дорівнює НСД числа й 0?

Будь-яке ціле число ділить 0, тому $\gcd(a, 0) = |a|$ . НСД чисел 0 і 0 не визначений.

Як знайти НСД трьох чисел?

Знайдіть НСД двох чисел, а потім НСД цього результату й третього числа. Для 24, 36 і 60: $\gcd(24, 36) = 12$ і $\gcd(12, 60) = 12$ .

Як НСД допомагає скорочувати дроби?

Поділіть чисельник і знаменник на їхній НСД, і дріб одразу стане нескоротним. Оскільки $\gcd(48, 180) = 12$ , отримуємо $\frac{48}{180} = \frac{4}{15}$ .

Спробуйте калькулятор НСД

Введіть свої числа та порівняйте розкладання на прості множники з алгоритмом Евкліда.

Відкрити калькулятор Запитати ШІ-розв'язувач

Про калькулятор НСД

Що таке найбільший спільний дільник?

Як користуватися калькулятором НСД

Формули

Алгоритм Евкліда

Через розкладання на прості множники

Зв'язок із НСК

Розв'язаний приклад: 48, 180

Відповідь

Як ми зрозуміли вашу задачу

Покроковий розв'язок

Використані формули

Перевірка

Докладне пояснення

Чому працює алгоритм Евкліда

Де потрібен НСД

Розкладання на множники чи алгоритм Евкліда

Типові помилки

Поради

Поширені запитання

Що таке найбільший спільний дільник?

НСД, GCD, GCF, HCF — це одне й те саме?

Як працює алгоритм Евкліда?

Чому дорівнює НСД чисел без спільних дільників?

Чи можна знайти НСД від'ємних чисел?

Чому дорівнює НСД числа й 0?

Як знайти НСД трьох чисел?

Як НСД допомагає скорочувати дроби?

Спробуйте калькулятор НСД

Інші математичні калькулятори