Kalkulator GCD i LCM

GCD, nazywany również największym wspólnym czynnikiem (GCF), to największa dodatnia liczba całkowita, która dzieli obie liczby bez reszty. Na przykład GCD liczb 12 i 18 wynosi 6, ponieważ 6 jest największą liczbą, która dzieli obie liczby równo.

LCM to najmniejsza dodatnia liczba całkowita, która jest podzielna przez obie liczby. Na przykład LCM liczb 4 i 6 wynosi 12, ponieważ 12 jest najmniejszą liczbą podzielną przez 4 i 6.

Dla dowolnych dwóch dodatnich liczb całkowitych a i b: GCD(a,b) × LCM(a,b) = a × b. Ta zależność pozwala obliczyć LCM, jeśli znasz GCD, lub odwrotnie.

GCD jest niezbędna do upraszczania ułamków (dzielenia licznika i mianownika przez ich GCD), rozwiązywania równań diofantycznych oraz różnych zastosowań w kryptografii i informatyce.

Aby uprościć ułamek, należy podzielić zarówno licznik, jak i mianownik przez ich GCD. Na przykład, aby uprościć ułamek 24/36: znajdź GCD(24,36) = 12, a następnie podziel oba ułamki przez 12, aby otrzymać 2/3. W ten sposób otrzymamy ułamek w najniższych wartościach.

LCM jest używane podczas synchronizacji powtarzających się zdarzeń. Przykłady obejmują ustalenie, kiedy dwa autobusy przyjeżdżają w tym samym czasie, określenie wspólnych mianowników do dodawania ułamków, planowanie powtarzających się zadań lub planowanie, kiedy koła zębate o różnej liczbie zębów ustawią się w jednej linii.

Rozłóż każdą liczbę na czynniki pierwsze, a następnie pomnóż wspólne czynniki przez najniższe potęgi. Na przykład 48 = 2^4 × 3 i 18 = 2 × 3^2. Wspólne czynniki to 2^1 i 3^1, więc GCD = 2 × 3 = 6.

Rozbij każdą liczbę na czynniki pierwsze, a następnie pomnóż wszystkie czynniki, używając najwyższych potęg. Dla 12 = 2^2 × 3 i 18 = 2 × 3^2, weź 2^2 i 3^2, więc LCM = 4 × 9 = 36.

Algorytm Euklidesa efektywnie znajduje GCD poprzez wielokrotne dzielenie i branie reszt. Dla GCD(48,18): 48÷18=2 reszta 12, 18÷12=1 reszta 6, 12÷6=2 reszta 0. Gdy reszta wynosi 0, ostatni dzielnik (6) jest GCD.