GCD and LCM Calculator

The two ideas behind simplifying fractions, finding common denominators, and working out when two repeating events coincide.

The Euclidean algorithm

The oldest algorithm still in everyday use, described by Euclid around 300 BC. To find the GCD of two numbers, repeatedly replace the larger with the remainder of dividing it by the smaller, until the remainder is zero. The last non-zero value is the GCD.

It is startlingly efficient: the number of steps grows only logarithmically with the size of the inputs, so numbers with hundreds of digits are handled in a fraction of a second. This efficiency is why it sits at the heart of RSA encryption and modular arithmetic generally.

LCM and the relationship between them

The lowest common multiple is the smallest number both inputs divide into exactly. It is easiest to compute from the GCD:

For 48 and 180: 48 × 180 = 8,640, divided by the GCD of 12 gives an LCM of 720.

The prime factorisation view makes the symmetry clear. Take the lowest power of each shared prime for the GCD, and the highest power of every prime appearing in either for the LCM. With 48 = 2⁴ × 3 and 180 = 2² × 3² × 5: GCD = 2² × 3 = 12, LCM = 2⁴ × 3² × 5 = 720.

Where they actually get used

• Simplifying fractions. Divide numerator and denominator by their GCD to reach lowest terms in one step.
• Adding fractions. The LCM of the denominators is the lowest common denominator, which keeps the arithmetic small.
• Coinciding cycles. Two buses leaving every 48 and 180 minutes next depart together after 720 minutes — twelve hours. Gear teeth, traffic lights and shift rotas all work this way.
• Cryptography. RSA key generation depends on finding numbers coprime to a modulus, and on the extended Euclidean algorithm to compute modular inverses.
• Tiling and packing. The largest square tile that fits a 48 × 180 cm area exactly is 12 cm — the GCD.