Euclidean algorithm — GCD computation

What is the Euclidean Algorithm?

Why does this work? The heart of the algorithm rests on one key property:

Formula Euclidean Lemma

For any integers $a, b$ with $b \neq 0$ : $\gcd(a, b) = \gcd(b, a \bmod b)$ Derivation from scratch:

Write the division algorithm: $a = bq + r$ where $0 \le r < b$ and $r = a \bmod b$ .
Let $d = \gcd(a, b)$ . Then $d \mid a$ and $d \mid b$ (by definition of GCD).
Since $r = a - bq$ , and $d$ divides both $a$ and $bq$ , we have $d \mid r$ . So $d$ is a common divisor of $b$ and $r$ .
Conversely, let $d' = \gcd(b, r)$ . Then $d' \mid b$ and $d' \mid r$ .
From $a = bq + r$ , since $d'$ divides $bq$ and $r$ , we have $d' \mid a$ . So $d'$ is a common divisor of $a$ and $b$ .
Therefore $d = d'$ , proving $\gcd(a, b) = \gcd(b, r) = \gcd(b, a \bmod b)$ . ∎

Why this step? We didn't assume anything magical—just used the definition of divisibility and the division algorithm. The remainder $r$ "inherits" all common divisors from $a$ and $b$ .

How to Execute the Algorithm

Step-by-step:

Start with two integers $a \ge b > 0$ .
Compute $r = a \bmod b$ .
If $r = 0$ , output $b$ as the GCD and stop.
Otherwise, replace $a \gets b$ and $b \gets r$ , then repeat from step 2.

Why does it terminate? Each iteration strictly decreases $b$ (since $r < b$ ), and $b$ is always non-negative. After finitely many steps, $r$ becomes zero.

Worked example Example 1:

$\gcd(48, 18)$ Goal: Find the GCD of 48 and 18. | Step | $a$ | $b$ | $a \bmod b$ | Why this step? | |------|------|-------------|------------------------------------------------| | 1 | 48 | 18 | 12 | $48 = 18 \cdot 2 + 12$ , so remainder is 12 | | 2 | 18 | 12 | 6 | $18 = 12 \cdot 1 + 6$ , so remainder is 6 | | 3 | 12 | 6 | 0 | $12 = 6 \cdot 2 + 0$ , remainder is 0, stop here |

Answer: $\gcd(48, 18) = 6$ .

Why this step? At each row, we're finding how many times $b$ fits into $a$ , then working with the leftover (remainder). When the remainder is 0, the last non-zero remainder is the GCD because it divides both numbers evenly.

Worked example Example 2:

$\gcd(1071, 462)$ Goal: Find GCD of two larger numbers.

| Step | $a$ | $b$ | $a \bmod b$ | Calculation | |------|-------|-------------|----------------------------------------| | 1 | 1071 | 462 | 147 | $1071 = 462 \cdot 2 + 147$ | | 2 | 462 | 147 | 21 | $462 = 147 \cdot 3 + 21$ | | 3 | 147 | 21 | 0 | $147 = 21 \cdot 7 + 0$ |

Answer: $\gcd(1071, 462) = 21$ .

Why this step? The algorithm keeps "peling off" multiples of the smaller number. The process is much faster than prime factorization (imagine factoring 1071!).

Time Complexity and Efficiency

How many steps does the Euclidean algorithm take?

Practical implication: For 1000-digit numbers, the algorithm takes roughly $5000$ steps—easily computable on a computer. Compare this to factoring, which is exponentially hard.

Common Mistakes

Extended Euclidean Algorithm (Preview)

The basic algorithm finds $\gcd(a, b)$ . The extended Euclidean algorithm also finds integers $x, y$ such that: $ax + by = \gcd(a, b)$

This is the Bézout's identity and is crucial for:

Finding modular inverses (used in RSA cryptography)
Solving linear Diophantine equations
Computing the LCM using $\text{lcm}(a, b) = \frac{ab}{\gcd(a, b)}$

(This is covered in the next note.)

Active Recall Practice

Recall Explain to a 12-year-old

Imagine you have two chocolate bars: one is 48 squares, the other is 18 squares. You want to break them into the biggest equal pieces that fit both bars perfectly (no leftovers).

Instead of guessing, use the leftover trick: break the big bar (48) using the small bar (18) as a measuring stick. You get 2 full small bars and 12 squares left over. Now forget the 48—just ask: "What's the biggest piece that fits both 18 and 12?"

Repeat: 18 using 12 gives full bar and 6 left over. Now: "What fits both 12 and 6?" That's easy—6 fits into 12 exactly twice, with 0 left over. Done! The answer is 6 squares.

Why does it work? Any piece that fits both the original bars MUST also fit the leftovers. So you can keep working with smaller and smaller numbers until you can't divide anymore. The last number standing is your answer.

Connections

2.5.01-divisibility-and-division-algorithm — The division algorithm $a = bq + r$ is the engine of Euclidean algorithm
2.5.03-fundamental-theorem-of-arithmetic — GCD relates to common prime factors, but Euclidean algorithm bypasses factorization
2.5.08-extended-euclidean-algorithm — Next step: finding Bézout coefficients $ax + by = \gcd(a, b)$
2.5.10-bezouts-identity — The existence guarantee that Euclidean algorithm exploits
2.5.15-modular-arithmetic-basics — GCD is key to finding modular inverses
3.2.04-rsa-encryption — RSA uses Euclidean algorithm to compute modular inverses for key generation
1.4.09-fibonacci-sequence — Worst-case Euclidean algorithm inputs are consecutive Fibonacci numbers

#flashcards/maths

What is the Euclidean algorithm? :: A recursive method to find $\gcd(a, b)$ by repeatedly replacing $(a, b)$ with $(b, a \bmod b)$ until $b = 0$ .

State the Euclidean Lemma :: $\gcd(a, b) = \gcd(b, a \bmod b)$ for any $b \neq 0$ .

Why does $\gcd(a, b) = \gcd(b, a \bmod b)$ ? :: Because any common divisor of $a$ and $b$ must divider = a - bq$ (the remainder), and vice versa. So the set of common divisors is identical.

What is the termination condition for Euclidean algorithm?

When

b = 0

, the algorithm stops and

a

is the GCD.

How many steps does Euclidean algorithm take for inputs up to

n

digits?

At most

O(n)

steps, specifically

\le 5n

by Lamé's Theorem. This is

O(\log b)

in terms of the input size.

What inputs give the worst-case (maximum steps) for Euclidean algorithm?

Consecutive Fibonacci numbers, where each quotient is 1, giving the slowest shrinkage of remainders.

Compute $\gcd(48, 18)$ using Euclidean algorithm :: $48 = 18 \cdot 2 + 12$ , $18 = 12 \cdot 1 + 6$ , $12 = 6 \cdot 2 + 0$ . Answer: $6$ .

True or False: Euclidean algorithm requires $a > b$ to work :: False. If $a < b$ , the first step swaps them automatically: $\gcd(a, b) = \gcd(b, a)$ .

How is LCM related to GCD?

\text{lcm}(a, b) = \frac{ab}{\gcd(a, b)}

. The Euclidean algorithm finds GCD, which then gives LCM.

Why is Euclidean algorithm faster than prime factorization for large numbers?

Factorization is exponential in the number of digits; Euclidean algorithm is polynomial (logarithmic steps), making it feasible for 100+ digit numbers used in cryptography.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Euclidean algorithm ek bohot smart tarika hai do numbers ka GCD (greatest common divisor) nikalne ka. Socho ki tumhare paas do chocolate bars hain—ek 48 pieces ka aur ek 18 pieces ka. Tum chahte ho ki dono ko sabse bade equal tukdon mein todo, jisme koi piece bacha na rahe. Normal tarike se hum prime factorization karenge (48 = 2⁴ × 3, 18 = 2 × 3², common factors leke GCD = 6), lekin agar numbers bohot bade hain (jaise 1000 digits), toh factorization bahut slow ho jata hai.

Euclidean algorithm ka magic yeh hai: remainder use karo. Pehle 48 ko 18 se divide karo: 48 = 18 × 2 + 12 (remainder 12 bacha). Ab purani 48 ko bhool jao, sirf 18 aur 12 ke bech GCD dhundho. Phir 18 = 12 × 1 + 6 (remainder 6). Ab 12 aur 6 ke beech GCD dhundho: 12 = 6 × 2 + 0 (remainder 0, matlab perfect division). Jab remainder 0 ho jaye, last non-zero remainder (yahan 6) hi tumhara GCD hai. Proof simple hai: agar koi number dono original numbers ko divide karta hai, toh woh remainder ko bhi divide karega (kyunki remainder = a - bq). Isliye har step mein common divisors ka set same rehta hai, bas numbers chhote hote jate hain.

Yeh algorithm itna powerful hai ki bade RSA encryption systems mein bhi use hota hai, jahan 100-200 digit numbers ka GCD seconds mein nikal sakte hain. Fibonacci numbers worst case hain—agar tum consecutive Fibonacci numbers ka GCD nikalo (jaise 89 aur 55), toh sabse zyada steps lagte hain, lekin phir bhi O(log b) time mein khatam ho jata hai. Engineering mein, cryptography mein, computer science mein—har jagah yeh algorithm fundamental hai. Ek baar samajh gaye toh kabhi bhoologe nahi, kyunki logic bilkul natural hai: bade problem ko baar baar chhota karte jao jab tak simple answer na mil jaye.

Euclidean algorithm — GCD computation

What is the Euclidean Algorithm?

How to Execute the Algorithm

Time Complexity and Efficiency

Common Mistakes

Extended Euclidean Algorithm (Preview)

Active Recall Practice

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Number Theory (Intermediate)

Connections