Euclidean algorithm — GCD computation: Question bank

Before we start, two words we lean on constantly:

Divides — we say $d$ divides $a$ (written $d ∣ a$ ) when $a$ is an exact multiple of $d$ , i.e. $a = d \cdot k$ for some whole number $k$ , no remainder. Picture $a$ as a row of dots that can be split into equal groups of size $d$ with none left over.
GCD — the greatest common divisor $g cd (a, b)$ is the biggest number that divides both $a$ and $b$ . Picture the largest tile that covers both an $a$ -length and a $b$ -length ruler with no gaps.

True or false — justify

The step-relation

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

only holds when

a > b

False — if

a < b

then

a mod b = a

, so it becomes

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

, which is trivially true and just swaps the pair. The relation holds for any order.

The Euclidean algorithm can fail to terminate for very large inputs

False — the second number strictly shrinks each step (

r < b

) and stays

\geq 0

, so it must hit

0

after finitely many steps no matter how large the start.

g cd (a, 0) = a

for every positive integer

a

True — every number divides

0

(since

0 = a \cdot 0

), so the largest divisor shared by

a

and

0

is just the largest divisor of

a

, which is

a

itself. This is the algorithm's stopping value.

The last remainder computed by the algorithm is the GCD

False — the last non-zero remainder is the GCD. The very last remainder is

0

, which is the signal to stop, not the answer.

g cd (a, b) = 1

the algorithm does no work, since they share nothing

False — coprime pairs can take the most steps (e.g. consecutive Fibonacci numbers like

89, 55

). "Sharing nothing but 1" still requires grinding the numbers down to reveal it.

Prime factorization and the Euclidean algorithm always give the same GCD

True — they compute the same quantity by different routes; only their speed differs. Euclid avoids factoring, which is why it scales to huge numbers.

Swapping the inputs,

g cd (a, b)

g cd (b, a)

, can change the number of steps taken

True (essentially) — if you feed the smaller number first, the algorithm spends one bonus step just swapping them, then proceeds identically. The final GCD is unchanged.

Spot the error

g cd (48, 18)

48 mod 18 = 12

, and since

12

is even, the GCD is

12

Wrong — you stopped too early. A non-zero remainder means continue: recurse on

g cd (18, 12)

. The remainder being even (or anything) is irrelevant; only reaching remainder

0

ends the process.

"Since

a = b q + r

, the GCD is the quotient

q

Wrong —

q

is how many times

b

fits into

a

and gets thrown away. The GCD lives in the remainder chain; it is the last non-zero

r

, never the quotient.

a mod b

can be negative when

a < b

, so I must sort inputs first."

Wrong — for

a < b

a = 0 \cdot b + a

gives remainder

a

, a valid value in

[0, b)

. The remainder is defined to be non-negative and less than

b

; no sorting needed.

"To speed things up I replaced

a mod b

with

a - b

(one subtraction)."

Not an error in correctness but in efficiency — subtracting one

b

at a time is the slow ancestor of Euclid. Using the full remainder (

a mod b

) does all those subtractions at once, giving the fast

O (lo g b)

behaviour.

"The algorithm output

b = 0

, so the GCD is

0

Wrong — when

b

becomes

0

the answer is the other variable

a

, not

b

. Reading off the zero itself is confusing the stopping flag with the result.

g cd (0, 0) = 0

so the algorithm handles it fine."

g cd (0, 0)

is a genuine edge case: every integer divides

0

, so there is no greatest common divisor — it's conventionally defined as

0

. The algorithm returns

0

, but you should know it's a definition, not a computed maximum.

Why questions

Why must any common divisor of

a

and

b

also divide

a mod b

Because

a mod b = a - b q

, and a divisor of both

a

and

b q

divides their difference. This inheritance is exactly why swapping to

(b, a mod b)

loses no common divisors.

Why does the set of common divisors stay identical at every step, not just the maximum?

The lemma shows divisibility flows both directions (

d ∣ a, b \Rightarrow d ∣ r

and

d^{'} ∣ b, r \Rightarrow d^{'} ∣ a

), so the full common-divisor set is preserved — hence its maximum, the GCD, is too.

Why is the worst case built from Fibonacci numbers?

The slowest shrinkage happens when every quotient is the smallest possible,

q = 1

, so

a = b + r

. That recurrence is the Fibonacci rule, so consecutive Fibonacci numbers maximise the step count for their size.

Why do cryptographers prefer Euclid over factorization for finding a GCD?

Euclid runs in time proportional to the number of digits (polynomial), while factoring large numbers is believed to be exponentially hard — the whole security of RSA leans on that gap.

Why does the division algorithm

a = b q + r

deserve to be called the "engine" here?

Every single step is one application of the division algorithm; producing

r

with

0 \leq r < b

is both what shrinks the problem and what guarantees termination.

Why can the Euclidean algorithm find a GCD without ever knowing the prime factors?

It only ever uses the relationship between differences and divisors, never the numbers' internal structure. The prime factorisation exists but is never needed — Euclid sidesteps it entirely.

Edge cases

What does the algorithm do when

b ∣ a

exactly (first remainder is

0

It stops immediately with

b

as the GCD — e.g.

g cd (20, 5) = 5

in a single step, because

5

already divides

20

What is

g cd (a, a)

and how many steps does it take?

It equals

a

, found in one step:

a mod a = 0

, so it stops instantly. A number's largest self-shared divisor is itself.

What happens if one input is

1

g cd (a, 1) = 1

always, because

1

divides everything and nothing bigger divides

1

. The remainder

a mod 1 = 0

ends it in one step.

Can the GCD ever exceed the smaller of the two inputs?

No — a common divisor must divide the smaller number, so it cannot be larger than it. Equality happens exactly when the smaller number divides the larger.

How does the algorithm handle negative inputs like

g cd (- 48, 18)

Divisibility ignores sign, so

g cd (- 48, 18) = g cd (48, 18) = 6

; in practice you take absolute values first, since the GCD is conventionally taken as positive.

g cd (a, b)

still well-defined the moment we reach

g cd (b, 0)

— have we "lost" information?

No information lost — every earlier step preserved the common-divisor set, so

g cd (b, 0) = b

is genuinely the GCD of the original pair. The chain of equal GCDs connects the start to the finish.

Recall One-line self-test

Cover every answer above. If you can state the reason (not just the verdict) for at least 20 of these, you've internalised the traps. The recurring theme: stop at $b = 0$ , read $a$ ; the GCD lives in the remainder chain, never the quotient.

Connections

2.5.7-euclidean-algorithm-gcd-computation — the parent this bank interrogates
2.5.01-divisibility-and-division-algorithm — the $a = b q + r$ engine behind every step
2.5.03-fundamental-theorem-of-arithmetic — the factorisation Euclid deliberately avoids
2.5.08-extended-euclidean-algorithm — extends this to find Bézout coefficients
2.5.10-bezouts-identity — the $a x + b y = g cd (a, b)$ payoff
1.4.09-fibonacci-sequence — the worst-case input family
3.2.04-rsa-encryption — why the speed gap over factoring matters