Калкулатор GCD и LCM

GCD, наричан още Greatest Common Factor (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): Когато остатъкът е 0, последният делител (6) е GCD.