HCF (GCD) — prime factorization method, Euclidean algorithm: Question bank

Definition Symbols used on this page (define before use)

Before any trap, pin down the notation so nothing is assumed:

List the primes $p_{1}, p_{2}, p_{3}, \dots$ (that's $2, 3, 5, 7, \dots$ ). Any number can be written using just these.
$α_{i}$ (Greek "alpha", index $i$ ) is the ==exponent of the $i$ -th prime $p_{i}$ in $a$ 's factorization==. So if $a = 360 = 2^{3} \cdot 3^{2} \cdot 5^{1}$ , then $α_{1} = 3$ (power of 2), $α_{2} = 2$ (power of 3), $α_{3} = 1$ (power of 5).
$β_{i}$ (Greek "beta") is the same idea for $b$ : the exponent of prime $p_{i}$ in $b$ 's factorization. For $b = 84 = 2^{2} \cdot 3^{1} \cdot 7^{1}$ , $β_{1} = 2, β_{2} = 1, β_{4} = 1$ ; missing primes get exponent $0$ .
$lcm (a, b)$ = Least Common Multiple = the smallest positive integer that both $a$ and $b$ divide into. Its recipe is the mirror of HCF: take each prime to its maximum exponent, $\prod_{i} p_{i}^{m a x (α_{i}, β_{i})}$ . (Full treatment: LCM — Least Common Multiple.)
In Euclid's step $a = b q + r$ , the quotient $q$ is ==how many whole times $b$ fits into $a$ == (the integer part of $a \div b$ ), and $r$ is what's left over, $0 \leq r < b$ . Example: $1071 = 462 \cdot q 2 + r 147$ — $462$ fits into $1071$ twice, leaving $147$ .
Absolute value / signs: the gcd is always a positive integer, so for negative inputs we silently use $∣ a ∣$ and $∣ b ∣$ . Thus $g cd (a, 0) = ∣ a ∣$ , and $g cd (- 12, 18) = g cd (12, 18)$ . Keep this in mind every time a number below could be negative.

The picture below makes the $min$ (HCF) vs $max$ (LCM) split visual — refer back to it whenever a trap talks about "exponents."

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

True or false — justify

Every common divisor of

a

and

b

also divides

g cd (a, b)

True. The gcd is not just the biggest common divisor — it is a multiple of every common divisor. Formally, writing each number by its prime exponents, a common divisor's exponent on each prime is

\leq min (α_{i}, β_{i})

, which is exactly the gcd's exponent, so it divides the gcd.

The gcd of two numbers can be larger than the smaller of the two numbers.

False. The gcd divides the smaller number, and a positive divisor of

n

is at most

n

. So

g cd (a, b) \leq min (a, b)

g cd (a, b) = 1

, then

a

and

b

share no prime factors at all.

True. Coprime means no shared prime; each shared prime would contribute a factor

> 1

to the gcd. This is exactly the definition of coprime (relatively prime).

g cd (a, b) = 1

means one of

a, b

must be prime.

False.

g cd (8, 9) = 1

yet neither

8

nor

9

is prime. Coprimality is about shared primes, not about being prime.

For any

n > 0

g cd (n, n) = n

True. Every prime in

n

appears at exactly the same exponent in both copies, so

min (α_{i}, α_{i}) = α_{i}

leaves them all — you keep

n

whole.

Multiplying both numbers by 5 multiplies their gcd by 5.

True. Scaling both by

k

adds the same exponents to every prime, so

g cd (k a, k b) = k g cd (a, b)

. Here

g cd (5 a, 5 b) = 5 g cd (a, b)

d ∣ a

and

d ∣ b

, then

d ∣ (a + b)

and

d ∣ (a - b)

True. Write

a = d m, b = d n

; then

a \pm b = d (m \pm n)

, still a multiple of

d

. This closure of divisibility under

\pm

is the engine behind Euclid's algorithm (the repeated-remainder trick — not to be confused with Euclid's lemma about primes).

g cd (a, b) \times lcm (a, b) = a \times b

holds for three numbers too, i.e.

g cd \cdot lcm = ab c

False. The two-number proof works because per prime

min (α, β) + max (α, β) = α + β

exactly. With three exponents,

min (α, β, γ) + max (α, β, γ)

ignores the middle value, so it no longer sums to

α + β + γ

. Counterexample

2, 2, 2

g cd = 2, lcm = 2

, product

4 \neq = 8

Spot the error

g cd (360, 84)

: prime 2 gives

max (3, 2) = 3

, prime 3 gives

max (2, 1) = 2

, so gcd

= 2^{3} \cdot 3^{2} = 72

Wrong tool — that's the LCM recipe. The HCF must divide both, so no exponent may exceed either number's; use

min

, giving

2^{2} \cdot 3^{1} = 12

"Euclid on

g cd (48, 36)

48 = 36 \cdot 1 + 12

, then

36 = 12 \cdot 3 + 0

, remainder is

0

, so

g cd = 0

The answer is the last non-zero remainder, not the zero itself. Here that is

12

— the divisor in the step where remainder became

0

g cd (360, 84)

should include prime 5 (it's in 360) at exponent

1

Prime 5 is absent from 84, so its exponent there is

0

and

min (1, 0) = 0

— it's dropped. A prime missing from either number cannot divide both.

"To run Euclid you must first prime-factorize both numbers."

The whole point of Euclid's algorithm is that it needs no factoring — just repeated division with remainder. That's why it's fast on huge numbers.

"Since HCF means Highest, we take the highest powers."

The word "Highest" describes the factor (the largest number dividing both), not the exponents. To divide both, each exponent must be the minimum. Mnemonic: HCF is Humble.

"Bézout says

a x + b y = g cd (a, b)

, so

x

and

y

are unique."

They're not unique. If

(x, y)

works, so does

(x + \frac{b}{g}, y - \frac{a}{g})

for

g = g cd (a, b)

— infinitely many solutions (see Diophantine Equations).

Why questions

Why does replacing

a

by the remainder

r = a - b q

never change the gcd?

Here

q

is the integer quotient (how many times

b

fits in

a

). Any

d

dividing

a

and

b

also divides

r = a - b q

; any

d

dividing

b

and

r

divides

a = b q + r

. Same set of common divisors ⇒ same greatest one, so

g cd (a, b) = g cd (b, r)

Why must the Euclidean algorithm always terminate?

Each step's remainder is strictly smaller and non-negative (

0 \leq r < b

). A decreasing sequence of non-negative integers cannot fall forever, so it must hit

0

Why does the prime-factorization method rely on the Fundamental Theorem of Arithmetic?

The method compares exponents prime-by-prime, which only makes sense if each number has one factorization. Fundamental Theorem of Arithmetic guarantees that uniqueness.

Why does taking the minimum exponent per shared prime give the largest common divisor?

A common divisor's exponent on each prime is capped by both numbers, i.e. by their minimum

min (α_{i}, β_{i})

. Choosing equality at that cap is the biggest allowed choice, so it's maximal.

Why is

g cd

so central to reducing fractions?

Dividing numerator and denominator by their gcd removes every shared factor at once, landing in lowest terms in one step. See Reducing Fractions to Lowest Terms.

Why do coprime numbers matter for RSA?

Modular inverses exist exactly when the gcd is

1

; Modular Arithmetic & RSA chooses an exponent coprime to a total so it can be "undone."

Edge cases

What is

g cd (a, 0)

and why?

It equals

∣ a ∣

(the absolute value, since gcd is always positive). Every integer divides

0

, so the divisors of

0

impose no upper limit; the largest divisor of

a

still wins —

a

itself (or

- a

made positive).

What is

g cd (0, 0)

and why is it defined by convention?

It is set to

0

by convention. Every integer divides

0

, so there is no largest common divisor to pick — the usual "greatest" definition breaks down. We patch this single degenerate case with

g cd (0, 0) = 0

, consistent with

g cd (a, 0) = ∣ a ∣

; the algorithm does not crash.

What is

g cd (1, n)

for any

n

It's

1

. The only positive divisor of

1

1

, so no common divisor can be bigger. Everything is coprime to

1

What is

g cd (p, q)

for two distinct primes

p, q

It's

1

. Distinct primes share no prime factor, so the only common divisor is

1

— they are coprime.

What is

g cd (n, k n)

where

n ∣ k n

It's

n

. Since

n

divides both, and no divisor of

n

exceeds

n

, the gcd is

n

itself. (When one number divides the other, the gcd is the divisor.)

If both numbers are equal to a prime

p

, what is their gcd and lcm?

g cd (p, p) = p

and

lcm (p, p) = p

. Check the identity:

p \cdot p = p^{2} = p \times p

. ✅ (See LCM — Least Common Multiple.)

How should you handle

g cd (- 12, 18)

Sign is irrelevant to divisibility, so use absolute values:

g cd (12, 18) = 6

. Gcd is defined as a positive integer.

Does

g cd (a, b) = g cd (b, a)

Yes. "Common divisor" is symmetric in

a

and

b

— the shared prime exponents don't care about order — so the operation is commutative.

Recall One-line self-test

Cover every answer above and re-derive the reason, not just the verdict. If you can say why for all edge cases and spot each error's root cause, you own the concept.

Connections

HCF (GCD) — prime factorization method, Euclidean algorithm — parent topic
Fundamental Theorem of Arithmetic — why prime-comparison is valid
LCM — Least Common Multiple — the max-exponent mirror
Prime Numbers & Factorization
Diophantine Equations — Bézout's non-uniqueness
Modular Arithmetic & RSA — coprimality → inverses
Reducing Fractions to Lowest Terms