Calculate GCD & LCM Easily

[EXEC: MICRO_CORE]

✖️ 1. Intuition of common divisors/multiples and finding GCD/LCM for multiple numbers

🔍 What GCD and LCM Actually Mean

GCD is the largest number that divides all given numbers evenly.
LCM is the smallest number that all given numbers divide into evenly.
To find GCD of multiple numbers, find GCD of first two, then GCD of that result with the next number.
To find LCM of multiple numbers, find LCM of first two, then LCM of that result with the next number.
Common divisors live below the numbers; common multiples live above them.

Example: For 12 and 18, divisors of 12 are [1, 2, 3, 4, 6, 12] and divisors of 18 are [1, 2, 3, 6, 9, 18], so GCD is 6. Multiples of 12 are [12, 24, 36, 48...] and multiples of 18 are [18, 36, 54...], so LCM is 36.

💡 GCD shrinks down to what fits both; LCM grows up to what holds both.

[EXEC: DEEP_COMPUTE]

1. Intuition of common divisors/multiples and finding GCD/LCM for multiple numbers

Common Divisors and Common Multiples

A common divisor of integers $a$ and $b$ is any integer $d$ that divides both $a$ and $b$ evenly (remainder zero). The greatest common divisor (GCD) is the largest such divisor. A common multiple of $a$ and $b$ is any integer $m$ that is divisible by both $a$ and $b$ . The least common multiple (LCM) is the smallest positive such multiple.

Intuition: The GCD captures the "largest shared building block" of numbers, while the LCM represents the "smallest shared destination" when counting by each number.

Core Rules:

GCD is always positive and divides all given numbers.
LCM is always positive and is divisible by all given numbers.
For multiple numbers, find GCD/LCM iteratively: $\text{GCD}(a, b, c) = \text{GCD}(\text{GCD}(a, b), c)$ .
Convention: $\text{GCD}(0, n) = n$ for any nonzero $n$ .

These concepts extend naturally to more than two numbers using the same definitions.

Example: For 12 and 18, common divisors are 1, 2, 3, 6, so GCD = 6. Common multiples include 36, 72, 108, so LCM = 36.

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

EXEC: ALGORITHM

Find the greatest common divisor (GCD) of 0 and 15.

DEEP_COMPUTE

ULTRA

[EXEC: MICRO_CORE]

✖️ 2. Finding GCD using the Euclidean algorithm and prime factorization matching

⚙️ Two Methods to Find GCD

Euclidean Algorithm: Divide larger by smaller, replace larger with remainder, repeat until remainder is zero.
The last non-zero remainder is the GCD.
Prime Factorization Method: Write both numbers as products of primes, then take the lowest power of each common prime.
Euclidean algorithm is faster for large numbers.
Prime factorization shows why the GCD works structurally.

Example: GCD of 48 and 18 using Euclidean: $48 = 18 \times 2 + 12$ , then $18 = 12 \times 1 + 6$ , then $12 = 6 \times 2 + 0$ , so GCD is 6. Using primes: $48 = 2^4 \times 3^1$ and $18 = 2^1 \times 3^2$ , so GCD is $2^1 \times 3^1 = 6$ .

💡 Euclidean shrinks by remainders; primes pick the smallest shared building blocks.

[EXEC: DEEP_COMPUTE]

2. Finding GCD using the Euclidean algorithm and prime factorization matching

Euclidean Algorithm and Prime Factorization for GCD

The Euclidean algorithm computes $\text{GCD}(a, b)$ by repeatedly replacing the larger number with the remainder of division: $\text{GCD}(a, b) = \text{GCD}(b, a \bmod b)$ until the remainder is zero. Alternatively, using prime factorization, write each number as a product of primes, then take the minimum exponent for each prime factor.

Intuition: The Euclidean algorithm efficiently "peels away" non-shared factors through division, while prime factorization directly identifies shared prime components.

Core Rules:

Euclidean step: If $a = bq + r$ , then $\text{GCD}(a, b) = \text{GCD}(b, r)$ .
Termination: When remainder becomes 0, the last nonzero remainder is the GCD.
Prime method: For $a = p_1^{e_1} p_2^{e_2} \cdots$ and $b = p_1^{f_1} p_2^{f_2} \cdots$ , take $\text{GCD} = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \cdots$ .

Both methods always yield the same result.

Example: $\text{GCD}(48, 18)$ : $48 = 18 \cdot 2 + 12$ , $18 = 12 \cdot 1 + 6$ , $12 = 6 \cdot 2 + 0$ , so GCD = 6.

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

EXEC: ALGORITHM

Two numbers are given by their prime factorizations: $A = 2^3 \cdot 5^1$ and $B = 2^2 \cdot 5^2$ .

Using the prime factorization method, calculate the greatest common divisor (GCD) of $A$ and $B$ .

DEEP_COMPUTE

ULTRA

[EXEC: MICRO_CORE]

✖️ 3. Finding LCM and understanding the fundamental relationship

🔗 LCM and the Golden Formula

Prime Factorization Method for LCM: Take the highest power of each prime that appears in either number.
Formula Method: $\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$ .
This formula works because GCD removes the overlap counted twice when multiplying.
For multiple numbers, apply LCM pairwise step by step.
The formula only works for two numbers at a time.

Example: For 12 and 18, $\text{GCD}(12, 18) = 6$ , so $\text{LCM}(12, 18) = \frac{12 \times 18}{6} = \frac{216}{6} = 36$ . Using primes: $12 = 2^2 \times 3^1$ and $18 = 2^1 \times 3^2$ , so LCM is $2^2 \times 3^2 = 36$ .

💡 GCD times LCM equals the product because overlap gets removed once.

[EXEC: DEEP_COMPUTE]

3. Finding LCM and understanding the fundamental relationship

LCM Computation and the GCD-LCM Relationship

The LCM can be computed using prime factorization by taking the maximum exponent for each prime, or via the formula $\text{LCM}(a, b) = \frac{a \cdot b}{\text{GCD}(a, b)}$ . This relationship holds because the product $a \cdot b$ counts all prime factors with their exponents added, while dividing by GCD removes the "double-counted" shared factors.

Intuition: The formula balances the total factor count: multiplying $a$ and $b$ overcounts shared primes, so dividing by GCD corrects this exactly once.

Core Rules:

Prime method: For $a = p_1^{e_1} p_2^{e_2} \cdots$ and $b = p_1^{f_1} p_2^{f_2} \cdots$ , take $\text{LCM} = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \cdots$ .
Fundamental identity: $\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b$ for all positive integers $a, b$ .
Special case: If $\text{GCD}(a, b) = 1$ (coprime), then $\text{LCM}(a, b) = a \cdot b$ .

This identity does NOT extend directly to three or more numbers.

Example: For 12 and 18, $\text{LCM} = \frac{12 \times 18}{6} = 36$ .

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

EXEC: ALGORITHM

Two numbers are 15 and 20. Their Greatest Common Divisor (GCD) is 5. Using the fundamental identity, calculate their Least Common Multiple (LCM).

DEEP_COMPUTE

ULTRA

[EXEC: MICRO_CORE]

✖️ 4. Applications: LCM scheduling word problems, gear ratio synchronization, and fraction simplification

🛠️ Real-World Uses of GCD and LCM

Scheduling problems: LCM tells when repeating events align again (buses, bells, cycles).
Gear synchronization: LCM of teeth counts gives when gears return to starting position.
Fraction simplification: Divide numerator and denominator by their GCD to reduce.
Tile/pattern problems: LCM finds smallest repeating unit that covers a space evenly.
GCD finds the largest equal group size when dividing items.

Example: Two buses leave every 12 and 18 minutes. They align again after LCM of 12 and 18 which is 36 minutes. To simplify $\frac{18}{48}$ , divide both by GCD of 18 and 48 which is 6, giving $\frac{3}{8}$ .

💡 LCM syncs repeating events; GCD breaks things into biggest equal chunks.

[EXEC: DEEP_COMPUTE]

4. Applications: LCM scheduling word problems, gear ratio synchronization, and fraction simplification

Practical Applications of GCD and LCM

LCM solves scheduling problems where events repeat at different intervals (find when they coincide) and gear synchronization (when teeth realign). GCD simplifies fractions by dividing numerator and denominator by their GCD, and solves problems requiring equal-sized groups from different quantities.

Intuition: LCM finds the "next common occurrence" in cyclic processes; GCD finds the "largest uniform partition" of quantities.

Core Rules:

Scheduling: If events occur every $a$ and $b$ time units, they coincide every $\text{LCM}(a, b)$ units.
Fraction simplification: $\frac{a}{b} = \frac{a / \text{GCD}(a,b)}{b / \text{GCD}(a,b)}$ is in lowest terms.
Gear synchronization: Gears with $a$ and $b$ teeth realign after $\text{LCM}(a, b)$ tooth movements.
Equal partitioning: Largest group size dividing quantities $a$ and $b$ evenly is $\text{GCD}(a, b)$ .

These applications rely on the fundamental properties of divisibility.

Example: Buses arriving every 12 and 18 minutes coincide every $\text{LCM}(12, 18) = 36$ minutes. Simplify $\frac{12}{18} = \frac{2}{3}$ using $\text{GCD}(12, 18) = 6$ .

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

EXEC: ALGORITHM

Two subway trains depart from the same station. Train A departs every 15 minutes, and Train B departs every 20 minutes. If they just departed together, in how many minutes will they next depart at the exact same time?

DEEP_COMPUTE

ULTRA

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

✖️ 1. Intuition of common divisors/multiples and finding GCD/LCM for multiple numbers

🔍 What GCD and LCM Actually Mean

1. Intuition of common divisors/multiples and finding GCD/LCM for multiple numbers

Common Divisors and Common Multiples

✖️ 2. Finding GCD using the Euclidean algorithm and prime factorization matching

⚙️ Two Methods to Find GCD

2. Finding GCD using the Euclidean algorithm and prime factorization matching

Euclidean Algorithm and Prime Factorization for GCD

✖️ 3. Finding LCM and understanding the fundamental relationship

🔗 LCM and the Golden Formula

3. Finding LCM and understanding the fundamental relationship

LCM Computation and the GCD-LCM Relationship

✖️ 4. Applications: LCM scheduling word problems, gear ratio synchronization, and fraction simplification

🛠️ Real-World Uses of GCD and LCM

4. Applications: LCM scheduling word problems, gear ratio synchronization, and fraction simplification

Practical Applications of GCD and LCM

AWAITING_CONFIRMATION