Euclidean Algorithm

Context: FIT1058_MOC · computes gcd by repeated reduction · subtraction sped up to remainder · extended to find Bézout coefficients

Quick Revision

• 🎯 Objective: compute $\gcd (a,b)$ by iterating $(a,b)\to (b,a\mathrm{mod}b)$ ➔ stop when $b\mid a$, output $b$.
• 📦 Core Components: reduction $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$ ➔ base case $b\mid a$ ➔ quotient $q$ saved for Extended Euclidean Algorithm.
• ⚡ Key Constraint: remainder form collapses $\lfloor a/b\rfloor$ subtractions into one $a\mathrm{mod}b$; terminates as $b$ strictly decreases.

📝 Core

1. The Reduction (Subtraction → Remainder)

• Identity ➔ $\gcd (a,b)=\gcd (b,a-b)$ (Greatest Common Divisor reduction theorem).
• Speed-up ➔ replace repeated $-b$ with a single $a\mathrm{mod}b$ ➔ $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$.
• Base case ➔ $b\mid a$ ⟹ output $b$.

2. Why It Works & Halts

• Correctness ➔ each step preserves the pair’s common divisors ⟹ final divisor = original $\gcd$.
• Termination ➔ second argument strictly decreases and stays $\ge 0$ ⟹ must reach $b\mid a$.
• Quotient saved ➔ $q=\lfloor a/b\rfloor$ recorded ➔ reused by Extended Euclidean Algorithm for Bézout $x,y$.

Key identities:

$\gcd (174,48)=\gcd (48,\underset{174\mathrm{mod}48}{\underbrace{30}})=\gcd (30,\underset{48\mathrm{mod}30}{\underbrace{18}})=\gcd (18,\underset{30\mathrm{mod}18}{\underbrace{12}})=\gcd (12,\underset{18\mathrm{mod}12}{\underbrace{6}})=6$

⚖️ Core Decision Matrix

Form	Step cost	When it hurts
Subtraction $\gcd (a,b-\dots )$	$\lfloor a/b\rfloor$ subtractions to one remainder	huge quotient ⟹ many steps
Remainder $a\mathrm{mod}b$	one modulo per step	none — the efficient form
Extended	remainder + a Bézout triple	slightly more bookkeeping

When It Flips: the remainder form runs in $O(\log \min (a,b))$ divisions (worst case: consecutive Fibonacci numbers). It is the standard test for Coprimality ($\gcd =1$) and, extended, computes modular inverses.

📊 Exam Execution Trace

Manual Execution Trace

$\gcd (252,198)$, iterating $(a,b)\to (b,a\mathrm{mod}b)$:

Step / State	$a$	$b$	$q=\lfloor a/b\rfloor$	$a\mathrm{mod}b$
0 (Init)	252	198	—	—
1	252	198	1	54
2	198	54	3	36
3	54	36	1	18
4	36	18	2	0 → $18\mid 36$

⚠️ Common Mistakes

• 💡 Keep going until $b\mid a$, don’t stop at the first small remainder ➔ the answer is the last divisor, not the last remainder; and record $q=\lfloor a/b\rfloor$ if the Bézout coefficients are wanted.

🧠 Active Recall

Why is the remainder form faster than the subtraction form, and why does it terminate?

• Hint: One modulo = many subtractions; monotone decrease.

Answer

• Short answer: $a\mathrm{mod}b$ does all $\lfloor a/b\rfloor$ subtractions at once; the second argument strictly decreases while staying $\ge 0$, so it reaches $b\mid a$.
• Why: Divisor-preserving ➔ every step keeps the pair’s common divisors, so the final divisor is the original $\gcd$.

Trace the Euclidean Algorithm on $\gcd (48,174)$.

• Hint: Iterate remainders to divisibility.

Answer

• Short answer: $174\mathrm{mod}48=30$, $48\mathrm{mod}30=18$, $30\mathrm{mod}18=12$, $18\mathrm{mod}12=6$; $6\mid 12$ ⟹ output $6$.
• Why: Last divisor ➔ the answer is the divisor at the base case $b\mid a$, not the last non-zero remainder computed mid-loop.

What does the extended algorithm add, and why keep the quotient $q$?

• Hint: Bézout bookkeeping.

Answer

• Short answer: It returns $x,y$ with $\gcd (a,b)=xa+yb$ (Integer Linear Combination).
• Why: Back-substitution ➔ each $q=\lfloor a/b\rfloor$ is reused to unwind the remainders into the coefficients — the basis of modular inverses.