HCF (GCD) — prime factorization method, Euclidean algorithm: Worked examples

The scenario matrix

Each row is one class of input. The last column names the example that covers it.

#	Case class	What's special / where beginners trip	Covered by
A	Ordinary two positives	baseline — both methods must agree	Ex 1
B	One divides the other	the smaller number is the answer	Ex 2
C	Coprime pair ( $g cd = 1$ )	no shared primes — answer is $1$ , not $0$	Ex 3
D	A zero input ( $g cd (a, 0)$ )	convention $g cd (a, 0) = a$ ; Euclid stops instantly	Ex 4
E	Negative number(s)	sign is irrelevant — divisors ignore sign	Ex 5
F	Both methods, big numbers	factoring is painful → Euclid wins	Ex 6
G	Three or more numbers	chain the pairwise gcd	Ex 7
H	Word problem (tiles / bags)	translate "largest equal group" → gcd	Ex 8
I	Exam twist: gcd·lcm identity	find lcm without listing multiples	Ex 9

Recall Two degenerate edges worth naming now

What is $g cd (0, 0)$ ? ::: Undefined / conventionally $0$ — every integer divides $0$ , so there is no largest common divisor. Never appears in exams as a valid answer. What is $g cd (a, a)$ ? ::: $a$ itself (for $a > 0$ ) — a number's largest divisor is itself, and it divides both copies.

Ex 1 — Case A: ordinary two positives

Worked example Compute

$g cd (84, 120)$ two ways Forecast first: both even, both divisible by $12$ ? Guess... then read on.

Method 1 — prime factorization.

Factor $84 = 2^{2} \cdot 3 \cdot 7$ . Why this step? The Fundamental Theorem of Arithmetic says this factorization is unique, so it is a fixed "fingerprint" we can compare.
Factor $120 = 2^{3} \cdot 3 \cdot 5$ . Why? We need the fingerprint of the second number to see which primes are shared.
Take each shared prime to the minimum exponent. Why the minimum? The gcd must divide both, so it cannot use a prime to a higher power than either number owns → the smaller exponent is the ceiling.
- prime $2$ : $min (2, 3) = 2$
- prime $3$ : $min (1, 1) = 1$
- prime $5$ : only in $120$ → exponent $min (1, 0) = 0$ → dropped
- prime $7$ : only in $84$ → dropped
$g cd = 2^{2} \cdot 3 = 12$ .

Method 2 — Euclid (must agree). $120 = 84 \cdot 1 + 36, 84 = 36 \cdot 2 + 12, 36 = 12 \cdot 3 + 0.$ Last non-zero remainder $= 12$ . ✅

Verify: $84/12 = 7$ and $120/12 = 10$ , both whole. And $g cd (7, 10) = 1$ (coprime), confirming we squeezed out everything — nothing larger than $12$ can divide both. Forecast of $12$ was right.

Ex 2 — Case B: one number divides the other

Ex 3 — Case C: coprime pair (answer is 1, not 0)

Ex 4 — Case D: a zero input

Ex 5 — Case E: negative numbers

Ex 6 — Case F: big numbers, factoring vs Euclid

The figure below shows why Euclid is the power tool: each step chops the pair down like a staircase, while factoring a large number is a search for hidden primes.

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

Ex 7 — Case G: three numbers

Ex 8 — Case H: word problem (tiles / bags)

The figure shows the physical picture: the gcd is the largest square tile that paves a rectangle exactly.

Worked example A hall floor is

$2040 cm \times 1512 cm$ . What is the side of the largest square tile that covers it with no cutting, and how many tiles are needed? Forecast: the tile side must divide both dimensions. Biggest such number = ? Guess whether it's more or less than $100$ cm.

Translate: "largest side dividing both $2040$ and $1512$ " $= g cd (2040, 1512)$ . Why gcd? A whole tile with side $s$ fits along a wall of length $L$ iff $s ∣ L$ . Fitting both walls needs $s$ dividing both; largest such $s$ is the gcd.
Euclid: $2040 = 1512 \cdot 1 + 528$ .
$1512 = 528 \cdot 2 + 456$ .
$528 = 456 \cdot 1 + 72$ .
$456 = 72 \cdot 6 + 24$ .
$72 = 24 \cdot 3 + 0$ → stop. Tile side $= 24$ cm.
Number of tiles $= \frac{2040}{24} \times \frac{1512}{24} = 85 \times 63 = 5355$ . Why multiply the two counts? $85$ tiles fit along the length, $63$ across the width; a rectangular grid holds length $\times$ width tiles.

Verify: $24 ∣ 2040$ ( $2040/24 = 85$ ✓), $24 ∣ 1512$ ( $1512/24 = 63$ ✓). Units: $cm \div cm =$ pure count, good. Total tile area $5355 \times 2 4^{2} = 3, 084, 480 cm^{2}$ , and $2040 \times 1512 = 3, 084, 480 cm^{2}$ — floor fully covered, no gaps. ✅

Ex 9 — Case I: exam twist using $g cd \cdot lcm = ab$

Worked example Given

$g cd (a, b) = 18$ and $lcm (a, b) = 1080$ with $a = 90$ , find $b$ . Forecast: will $b$ be bigger or smaller than $90$ ? Guess.

Use the identity $g cd (a, b) \cdot lcm (a, b) = a \cdot b$ (proved in the parent from $min + max = α + β$ ; see LCM — Least Common Multiple). Why this identity and not raw factoring? We are given the gcd and lcm, so the identity lets us solve for the unknown directly — no need to factor anything.
Plug in: $18 \cdot 1080 = 90 \cdot b$ , so $19440 = 90 b$ .
Solve: $b = 19440/90 = 216$ . Why is this valid? The identity is an exact equality of integers, so dividing both sides by $90$ (which divides $19440$ ) gives the unique $b$ .
$b = 216$ .

Verify: Factor to double-check: $90 = 2 \cdot 3^{2} \cdot 5$ , $216 = 2^{3} \cdot 3^{3}$ . $g cd = 2^{m i n (1, 3)} 3^{m i n (2, 3)} 5^{m i n (1, 0)} = 2 \cdot 9 = 18$ ✓. $lcm = 2^{m a x (1, 3)} 3^{m a x (2, 3)} 5^{m a x (1, 0)} = 8 \cdot 27 \cdot 5 = 1080$ ✓. Both match — $b = 216$ , larger than $90$ . Forecast check!

Recap — did we cover every cell?

Recall Self-test: name the covered case for each answer

$g cd (84, 120) = ?$ ::: $12$ (Case A, ordinary positives) $g cd (9, 45) = ?$ ::: $9$ (Case B, one divides the other) $g cd (35, 24) = ?$ ::: $1$ (Case C, coprime) $g cd (17, 0) = ?$ ::: $17$ (Case D, zero input) $g cd (- 48, 36) = ?$ ::: $12$ (Case E, negatives → use absolute value) $g cd (2244, 418) = ?$ ::: $22$ (Case F, big numbers by Euclid) $g cd (72, 120, 156) = ?$ ::: $12$ (Case G, three numbers chained) Largest tile for $2040 \times 1512$ ? ::: side $24$ cm, $5355$ tiles (Case H, word problem) If $g cd = 18$ , $lcm = 1080$ , $a = 90$ then $b = ?$ ::: $216$ (Case I, identity twist)

Connections

HCF (GCD) — prime factorization method, Euclidean algorithm — parent: builds both methods
Fundamental Theorem of Arithmetic — why prime fingerprints are unique
LCM — Least Common Multiple — Ex 9 uses the $g cd \cdot lcm = ab$ bridge
Prime Numbers & Factorization — the factoring cross-checks
Reducing Fractions to Lowest Terms — coprime quotients = lowest terms (Ex 3)
Diophantine Equations — solvability rests on the gcd
Modular Arithmetic & RSA — coprimality (Ex 3) is the RSA gateway