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

НСД — це найбільше додатне ціле число, яке ділить усі задані числа без залишку.

Використовуйте алгоритм Евкліда для ефективного обчислення: повторно діліть і знаходьте залишок, доки не дійдете до 0.

НСК — це найменше додатне ціле число, яке ділиться на всі задані числа.

Обчислюйте за допомогою розкладу на прості множники (беріть найвищі степені) або за формулою: НСК = (a × b) / НСД.

НСД (найбільший спільний дільник) — це найбільше ціле число, на яке рівно ділиться кожне задане число, тоді як НСК (найменше спільне кратне) — це найменше додатне ціле число, на яке кожне задане число ділиться без залишку.

Вони спрямовані в протилежні боки: НСД шукає найбільший спільний дільник унизу, а НСК — найменший спільний кратний угорі. Для чисел 12 і 18 НСД дорівнює 6, а НСК — 36.

Згідно з Wolfram MathWorld, НСД також записується як gcd(a, b) або (a, b), а термін «найбільший спільний дільник» (НСД) є звичним синонімом для цієї самої величини.

Алгоритм Евкліда знаходить НСД шляхом багаторазової заміни більшого числа на залишок від ділення його на менше, зупиняючись, коли залишок досягає нуля; останній ненульовий залишок і є НСД.

Для 48 та 18: 48 = 2×18 + 12, потім 18 = 1×12 + 6, потім 12 = 2×6 + 0, отже, gcd(48, 18) = 6.

Енциклопедія Британніка зазначає, що цей метод бере початок з "Начал" Евкліда (бл. 300 р. до н. е.), що робить його одним із найстаріших алгоритмів, які досі використовуються щодня. Його ефективність є причиною того, чому програмні бібліотеки використовують його замість факторизації великих чисел.

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

Для 12 = 2²×3 та 18 = 2×3² візьміть 2² та 3², що дасть НСК = 4×9 = 36. Для НСД натомість беріть кожен спільний простий множник у найнижчому степені: 2¹×3¹ = 6.

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

Для будь-яких двох додатних цілих чисел a та b LCM(a, b) × GCD(a, b) = a × b. Ця тотожність дозволяє обчислити одну величину через іншу: LCM(a, b) = (a × b) / GCD(a, b).

Для 12 та 18 НСД дорівнює 6, тому НСК = (12 × 18) / 6 = 216 / 6 = 36, і дійсно 6 × 36 = 216 = 12 × 18.

Wolfram MathWorld документує це співвідношення як стандартний міст між двома функціями. Зауважте, що формула діє лише для двох чисел; для трьох і більше ви застосовуєте її попарно, а не припускаєте, що добуток дорівнює НСК × НСД.

Для трьох або більше чисел застосовуйте НСД чи НСК попарно: обчисліть результат для перших двох, потім об'єднайте його з наступним числом і так далі.

Наприклад, gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6, а lcm(4, 6, 8) = lcm(lcm(4, 6), 8) = lcm(12, 8) = 24. Обидві операції є асоціативними, тому порядок групування не змінює відповіді.

Цей калькулятор обробляє пакети автоматично, але швидкий шлях НСК×НСД = добуток не поширюється на три або більше вхідних даних — на чому наголошує Wolfram MathWorld.

Два числа є взаємно простими (coprime), коли їхній НСД дорівнює 1, що означає відсутність спільних простих множників, навіть якщо жодне з них не є простим саме по собі.

Наприклад, gcd(8, 15) = 1: 8 = 2³ та 15 = 3×5 не мають спільних простих множників, тому вони взаємно прості. Коли числа взаємно прості, їхній НСК дорівнює їхньому добутку; lcm(8, 15) = 120 = 8×15.

Wolfram MathWorld зазначає, що взаємна простота лежить в основі модульної арифметики та криптографії RSA, де генерація ключів вимагає експоненти, взаємно простої з функцією Ейлера. Взаємна простота є властивістю пари, а не окремих чисел.

НСК і НСД з'являються далеко за межами підручників.

НСД спрощує дроби до найменших значень (12/18 скорочується до 2/3 після ділення на 6) і знаходить найбільші рівні за розміром групи під час розподілу предметів — а після того, як ці групи зафіксовано, калькулятор факторіалів підраховує способи розташування елементів усередині кожної з них.

НСК знаходить, коли повторювані події збігаються, наприклад, два автобуси, що відправляються кожні 12 і 18 хвилин, зустрічаються знову через 36 хвилин, а також він дає спільний знаменник для додавання дробів.

Інженери використовують НСД у розробці передавальних чисел і зубчастих ременів, тоді як криптографи покладаються на перевірки взаємної простоти (НСД = 1) під час налаштування ключів RSA, як описує Енциклопедія Британніка у своєму огляді застосувань теорії чисел.

Тотожність Безу стверджує, що для цілих чисел a та b існують такі цілі числа x та y, що ax + by = gcd(a, b).

Для 12 та 18 НСД дорівнює 6, і одним із розв'язків є 12×(−1) + 18×(1) = −12 + 18 = 6. Розширений алгоритм Евкліда обчислює ці коефіцієнти під час обчислення НСД, що якраз і є способом знаходження модульних обернених елементів у криптографії.

Wolfram MathWorld та Цифрова бібліотека математичних функцій NIST розглядають тотожність Безу як наріжний результат елементарної теорії чисел, оскільки вона гарантує існування лінійної комбінації, що дорівнює НСД.

Кілька поширених помилок заважають людям під час обчислення НСК і НСД:

• Частою помилкою є плутанина між ними: НСД ніколи не більший за найменше вхідне число, тоді як НСК ніколи не менший за найбільше вхідне число, тому перевіряйте свою відповідь за цими межами.

• Інша помилка — припущення, що НСК × НСД = добуток працює для трьох чи більше чисел, хоча це не так.

• Люди також забувають, що НСД і НСК визначені для додатних цілих чисел, а не для дробів чи десяткових дробів, тому вхідні дані мають бути цілими числами.

• Нарешті, коли числа взаємно прості, пам'ятайте, що НСД дорівнює 1 (а не 0), а НСК дорівнює їхньому добутку.

Перевірка за допомогою тотожності НСК×НСД = a×b допомагає уникнути більшості помилок з двома числами.