Kalkulator GCD in LCM

GCD, imenovan tudi največji skupni faktor (GCF), je največje pozitivno celo število, ki deli obe števili brez ostanka. Na primer, GCD 12 in 18 je 6, ker je 6 največje število, ki enakomerno deli obe števili.

LCM je najmanjše pozitivno celo število, ki je deljivo z obema številoma. Na primer, LCM 4 in 6 je 12, ker je 12 najmanjše število, deljivo s 4 in 6.

Za kateri koli dve pozitivni celi števili a in b: GCD(a,b) × LCM(a,b) = a × b. To razmerje omogoča izračun LCM, če poznamo GCD, ali obratno.

GCD je bistvenega pomena za poenostavljanje ulomkov (deljenje števca in imenovalca z njunim GCD), reševanje diofantskih enačb ter različne aplikacije v kriptografiji in računalništvu.

Če želite poenostaviti ulomek, števec in imenovalec delite z njuno GCD. Na primer, če želite poenostaviti 24/36: poiščite GCD(24,36) = 12, nato oba delite z 12 in dobite 2/3. Tako dobimo ulomek v najnižjih vrednostih.

LCM se uporablja pri sinhronizaciji ponavljajočih se dogodkov. Primeri vključujejo ugotavljanje, kdaj dva avtobusa pripeljeta ob istem času, določanje skupnih imenovalcev za seštevanje ulomkov, načrtovanje ponavljajočih se nalog ali načrtovanje, kdaj se zobniki z različnim številom zob uskladijo.

Vsako število razdelite na prafaktorje, nato pa skupne faktorje pomnožite z najnižjimi potencami. Na primer 48 = 2^4 × 3 in 18 = 2 × 3^2. Skupna faktorja sta 2^1 in 3^1, zato je GCD = 2 × 3 = 6.

Vsako število razdelite na prafaktorje, nato pa vse faktorje pomnožite z najvišjimi potencami. Za 12 = 2^2 × 3 in 18 = 2 × 3^2 vzemite 2^2 in 3^2, torej LCM = 4 × 9 = 36.

Evklidski algoritem učinkovito najde GCD z večkratnim deljenjem in jemanjem ostankov. Za GCD(48,18): Ko je ostanek 0, je zadnji delitelj (6) GCD.