GCD & LCM Calculator

The Euclidean Algorithm is based on the principle that the greatest common divisor of two integers $a$ and $b$ ($a > b$) is identical to the greatest common divisor of $b$ and $a \pmod b$.

$$\text{GCD}(a, b) = \text{GCD}(b, a \pmod b)$$

Repeating this division until the remainder reaches $0$ yields the final non-zero remainder as the GCD.

• Example: Compute $\text{GCD}(1071, 462)$

Step 1: $1071 = 462 \times 2 + 147$ $\rightarrow$ $\text{GCD}(1071, 462) = \text{GCD}(462, 147)$

Step 2: $462 = 147 \times 3 + 21$ $\rightarrow$ $\text{GCD}(462, 147) = \text{GCD}(147, 21)$

Step 3: $147 = 21 \times 7 + 0$ (Remainder is 0)

Result: $\text{GCD}(1071, 462) = 21$.

For any two positive integers $a$ and $b$, the product of the numbers equals the product of their GCD and LCM:

$$a \times b = \text{GCD}(a, b) \times \text{LCM}(a, b)$$

Consequently, the LCM can be derived directly with a single arithmetic operation:

$$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$$

Note: This closed-form multiplication identity holds strictly for two numbers. For three or more numbers ($a, b, c$), compute sequentially: $\text{LCM}(a, b, c) = \text{LCM}(\text{LCM}(a, b), c)$.

Decomposing numbers into their canonical prime power representations offers intuitive structural clarity.

• $24 = 2^3 \times 3^1$

• $36 = 2^2 \times 3^2$

• GCD: Take the minimum exponent for each shared prime factor:

$\text{GCD} = 2^{\min(3, 2)} \times 3^{\min(1, 2)} = 2^2 \times 3^1 = 12$

• LCM: Take the maximum exponent across all prime factors present:

$\text{LCM} = 2^{\max(3, 2)} \times 3^{\max(1, 2)} = 2^3 \times 3^2 = 72$

• Sharing snacks equally with friends without leftovers (GCD): You have 24 apples and 36 oranges. What is the maximum number of friends you can share with equally? $\text{GCD}(24, 36) = 12$ friends, each receiving exactly 2 apples and 3 oranges.

• Bus and subway synchronized meeting times (LCM): A bus arrives every 8 minutes and a subway train arrives every 12 minutes. If both departed together at 7:00 AM, when will they depart together again? $\text{LCM}(8, 12) = 24$ minutes, meaning they depart together at 7:24 AM.

• Tiling a rectangular room with largest square tiles (GCD): You want to tile a 180cm by 120cm bathroom floor using identical square tiles without cutting any tile. The largest possible square tile size is $\text{GCD}(180, 120) = 60\text{cm}$, fitting exactly 6 tiles (3 across × 2 down).

• Medication and vitamin schedules (LCM): You take Vitamin A every 6 days and Vitamin B every 8 days. If you took both today, in how many days will you take both on the same day again? In $\text{LCM}(6, 8) = 24$ days.

• Matching hot dog buns and sausages (LCM): Sausages are sold in packs of 10, and buns in packs of 8. How many hot dogs must you make so no buns or sausages are left over? $\text{LCM}(10, 8) = 40$ hot dogs (4 packs of sausages and 5 packs of buns).

• Fraction Simplification and Common Denominators: Simplifying $\frac{18}{24}$ requires dividing numerator and denominator by $\text{GCD}(18, 24) = 6 \rightarrow \frac{3}{4}$. Finding common denominators for $\frac{1}{8} + \frac{1}{12}$ requires $\text{LCM}(8, 12) = 24$.

• Display Aspect Ratio Simplification: Simplifying $1920 \times 1080$ resolution by $\text{GCD}(1920, 1080) = 120$ derives the canonical $16:9$ aspect ratio.

• Gear Ratio and Cycle Synchronization: Two interlocking gears with 15 and 20 teeth return to starting alignment every $\text{LCM}(15, 20) = 60$ tooth passes.

• RSA Public-Key Cryptography: Selecting an encryption key $e$ coprime to Euler totient $\phi(n)$ is verified via the Extended Euclidean Algorithm.

• Cron Batch Task Scheduling: Avoiding simultaneous DB lock contention between background workers with different periods by computing LCM intervals.

Two integers $a$ and $b$ are defined as coprime (relatively prime) if their greatest common divisor is 1: $\text{GCD}(a, b) = 1$.

• Any two consecutive integers ($n, n+1$) are always coprime (e.g. 14 & 15).

• Any two distinct prime numbers are coprime (e.g. 13 & 19).

• When $a$ and $b$ are coprime, their LCM simplifies to their direct product: $\text{LCM}(a, b) = a \times b$.