Калькулятор GCD та LCM

GCD, який також називають найбільшим спільним множником (GCF), — це найбільше додатне ціле число, на яке обидва числа діляться без остачі. Наприклад, GCD чисел 12 і 18 дорівнює 6, адже 6 — найбільше число, на яке обидва діляться без остачі.

LCM — це найменше додатне ціле число, яке ділиться на обидва числа. Наприклад, LCM чисел 4 і 6 дорівнює 12, адже 12 — найменше число, яке ділиться і на 4, і на 6.

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

GCD необхідний для скорочення дробів (поділіть чисельник і знаменник на їхній GCD), розв’язання діофантових рівнянь і різних задач у криптографії та інформатиці.

Щоб скоротити дріб, поділіть чисельник і знаменник на їхній GCD. Наприклад, щоб скоротити 24/36: знайдіть GCD(24,36) = 12, а потім поділіть обидва числа на 12, щоб отримати 2/3. Так ви отримаєте нескоротний дріб.

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

Розкладіть кожне число на прості множники, а потім перемножте спільні множники з найменшими степенями. Наприклад, 48 = 2^4 × 3 і 18 = 2 × 3^2. Спільні множники — 2^1 і 3^1, тому GCD = 2 × 3 = 6.

Розкладіть кожне число на прості множники, а потім перемножте всі множники, використовуючи найвищі степені. Для 12 = 2^2 × 3 і 18 = 2 × 3^2 візьміть 2^2 і 3^2, тому LCM = 4 × 9 = 36.

Алгоритм Евкліда швидко знаходить GCD, послідовно ділячи числа й обчислюючи остачі. Для GCD(48,18): 48÷18=2 остача 12, 18÷12=1 остача 6, 12÷6=2 остача 0. Коли остача дорівнює 0, останній дільник (6) і є GCD.

Взаємно прості числа не мають спільних множників, крім 1. Для таких чисел GCD = 1, а LCM дорівнює їхньому добутку. Наприклад, 8 і 15 — взаємно прості: GCD(8,15) = 1, а LCM(8,15) = 120.