GCD- & LCM-rekenmachine

GCD, ook wel Greatest Common Factor (GCF) genoemd, is het grootste positieve gehele getal dat beide getallen deelt zonder rest. Bijvoorbeeld, GCD van 12 en 18 is 6 omdat 6 het grootste getal is dat beide evenredig deelt.

LCM is het kleinste positieve gehele getal dat deelbaar is door beide getallen. Bijvoorbeeld, LCM van 4 en 6 is 12 omdat 12 het kleinste getal is dat deelbaar is door zowel 4 als 6.

Voor twee positieve gehele getallen a en b geldt: GCD(a,b) × LCM(a,b) = a × b. Met deze relatie kun je LCM berekenen als je GCD weet, of andersom.

GCD is essentieel voor het vereenvoudigen van breuken (deel teller en noemer door hun GCD), het oplossen van Diophantijnse vergelijkingen en verschillende toepassingen in cryptografie en computerwetenschap.

Om een breuk te vereenvoudigen, deel je zowel de teller als de noemer door hun GCD. Bijvoorbeeld, om 24/36 te vereenvoudigen: zoek GCD(24,36) = 12, deel dan beide door 12 om 2/3 te krijgen. Dit geeft je de breuk in zijn laagste termen.

LCM wordt gebruikt bij het synchroniseren van herhalende gebeurtenissen. Voorbeelden hiervan zijn het vinden wanneer twee bussen op hetzelfde moment aankomen, het bepalen van gemene delers voor het optellen van breuken, het plannen van terugkerende taken of het plannen wanneer tandwielen met verschillende tandtellingen uitgelijnd zijn.

Verdeel elk getal in priemfactoren en vermenigvuldig dan de gemeenschappelijke factoren met de laagste machten. Bijvoorbeeld, 48 = 2^4 × 3 en 18 = 2 × 3^2. Gemeenschappelijke factoren zijn 2^1 en 3^1, dus GCD = 2 × 3 = 6.

Verdeel elk getal in priemfactoren en vermenigvuldig alle factoren met de hoogste macht. Voor 12 = 2^2 × 3 en 18 = 2 × 3^2, neem 2^2 en 3^2, dus LCM = 4 × 9 = 36.

Het Euclidische algoritme vindt GCD efficiënt door herhaaldelijk te delen en resten te nemen. Voor GCD(48,18): 48÷18=2 rest 12, 18÷12=1 rest 6, 12÷6=2 rest 0. Als de rest 0 is, is de laatste deler (6) de GCD.