Day 72 — Euclidean algorithm & extended Euclid

Updated

July 30, 2026

Day 72 — Euclidean algorithm and the extended Euclidean algorithm

Stage VII · concept day
Goal: Compute \(\gcd\) by Euclid’s algorithm; prove correctness via the remainder invariant; understand \(O(\log n)\) complexity and Fibonacci worst case; run extended Euclid; prove Bézout; prepare modular inverses.

Why this matters

The Euclidean algorithm is one of the oldest and most important algorithms in mathematics. In CS literacy it underpins modular inverses (Day 74), fraction reduction, and the algebra behind RSA’s key equations (Day 77). Extended Euclid turns “\(\gcd=1\)” into an explicit integer combination — the constructive heart of Bézout’s identity.

Note

No labs. Hand-trace every table. Optional calculator only to verify multiplications after the fact.

Theory

gcd definition

Definition. For integers \(a,b\) not both zero, \(\gcd(a,b)\) is the largest positive integer \(d\) such that \(d\mid a\) and \(d\mid b\). Convention: \(\gcd(a,b)=\gcd(|a|,|b|)\). We avoid \(\gcd(0,0)\) (undefined or \(0\) depending on system).

Symmetry. \(\gcd(a,b)=\gcd(b,a)\).

Key identity (the invariant)

Lemma (gcd recurrence). For any integers \(a,b\) with \(b\neq 0\), and any integer \(q\), \[ \gcd(a,b)=\gcd(b,\, a-qb). \] In particular, if \(a=bq+r\) (division algorithm), then \[ \gcd(a,b)=\gcd(b,r)=\gcd(b,\, a\bmod b). \]

Proof. Any common divisor of \(a\) and \(b\) divides \(a-qb\), hence divides \(r\). Conversely any common divisor of \(b\) and \(r\) divides \(bq+r=a\). So the sets of common divisors coincide; the greatest positives match.

This identity is the loop invariant of Euclid: each replacement preserves the gcd of the current pair.

Euclidean algorithm

Algorithm (Euclid). Input: integers \(a,b\ge 0\), not both zero. (WLOG start with any order.)

  1. While \(b\neq 0\): replace \((a,b)\) by \((b,\, a\bmod b)\).
  2. Return \(a\).

Theorem (correctness). The algorithm terminates and returns \(\gcd(a,b)\).

Proof.
- Termination: each remainder satisfies \(0\le r < b\), so the second coordinate is a strictly decreasing sequence of nonnegative integers. It cannot descend forever.
- Correctness: by the gcd recurrence, \(\gcd\) is invariant under each replacement. When \(b=0\), \(\gcd(a,0)=a\) (for \(a>0\); if both start zero we excluded). By induction on the number of steps, the return value is the original gcd.

Complexity: \(O(\log n)\) and Fibonacci worst case

Lamé’s theorem (statement). If \(a>b\ge 1\) and Euclid takes \(k\) division steps (nonzero remainders), then \(b\ge F_{k+1}\) (Fibonacci, with \(F_1=1,F_2=1,F_3=2,\ldots\)). Consequently the number of steps is \(O(\log b)\).

Worst-case intuition. Consecutive Fibonacci numbers force remainders to drop as slowly as possible: Euclid on \((F_{n+1},F_n)\) produces the previous Fibonacci pair at each step. Since \(F_n\sim \varphi^n/\sqrt{5}\) with \(\varphi=(1+\sqrt{5})/2\), we need \(n=\Theta(\log F_n)\) steps.

Bit-complexity literacy. Each division on numbers of size \(O(\log n)\) bits is itself not free in a multi-tape model, but for this volume the takeaway is: Euclid is logarithmic in the magnitude, vastly faster than trial division up to \(\min(|a|,|b|)\).

Bézout’s identity

Theorem (Bézout). For any \(a,b\in\mathbb{Z}\) not both zero, there exist integers \(x,y\) (Bézout coefficients) such that \[ ax + by = \gcd(a,b). \] Moreover, the set of all integer linear combinations \(\{ax+by:x,y\in\mathbb{Z}\}\) equals exactly the set of multiples of \(d=\gcd(a,b)\).

Proof that combinations = \(d\mathbb{Z}\).
Let \(I=\{ax+by:x,y\in\mathbb{Z}\}\). \(I\) is nonempty and closed under addition and subtraction. Let \(d^*\) be the least positive element of \(I\) (well-ordering of positive integers). Division: any \(z\in I\) is a multiple of \(d^*\) (else remainder would be a smaller positive element of \(I\)). In particular \(d^*\mid a\) and \(d^*\mid b\) (take \(x=1,y=0\) and \(x=0,y=1\)), so \(d^*\le d=\gcd(a,b)\). But \(d\) divides every combination, so \(d\mid d^*\) and \(d^*\ge d\). Thus \(d^*=d\), and \(I=d\mathbb{Z}\). In particular \(d\in I\), giving Bézout coefficients.

Corollary. \(\gcd(a,b)=1\) iff there exist \(x,y\) with \(ax+by=1\).

Corollary (Euclid’s lemma via Bézout). If \(p\) prime, \(p\mid ab\), \(p\nmid a\), then \(p\mid b\). (Day 71 sketch now fully justified.)

Extended Euclidean algorithm

Run Euclid while recording quotients, then express the gcd as a combination of the original \(a,b\).

Method 1 — back-substitution. Write each remainder as a combination of previous two lines until the gcd is a combination of \(a\) and \(b\).

Method 2 — tabular (recommended). Maintain coefficients so each remainder \(r_i = a s_i + b t_i\).

Initialize:

\(i\) \(r_i\) \(q_i\) \(s_i\) \(t_i\)
\(-1\) \(a\) — \(1\) \(0\)
\(0\) \(b\) — \(0\) \(1\)

While \(r_i\neq 0\): \(q_{i+1}=\lfloor r_{i-1}/r_i\rfloor\), \(r_{i+1}=r_{i-1}-q_{i+1}r_i\), and \[ s_{i+1}=s_{i-1}-q_{i+1}s_i,\qquad t_{i+1}=t_{i-1}-q_{i+1}t_i. \] When \(r_{k+1}=0\), we have \(r_k=\gcd\) and \(r_k=a s_k + b t_k\).

Linear Diophantine equations

Theorem. The equation \(ax+by=c\) has integer solutions \((x,y)\) iff \(\gcd(a,b)\mid c\).

If \(d=\gcd(a,b)\) and \(x_0,y_0\) satisfy \(ax_0+by_0=d\), then one particular solution of \(ax+by=c\) is \[ x^*=x_0\cdot\frac{c}{d},\qquad y^*=y_0\cdot\frac{c}{d}. \] The general solution (for \(ab\neq 0\)) is \[ x=x^* + \frac{b}{d}k,\qquad y=y^* - \frac{a}{d}k,\qquad k\in\mathbb{Z}. \]

Verification. The homogeneous equation \(ax+by=0\) has solutions \(x=(b/d)k\), \(y=-(a/d)k\); adding a particular solution yields the full lattice of solutions.

Connection to modular inverses (preview Day 74)

If \(\gcd(a,m)=1\), Bézout gives \(ax+my=1\), so \(ax\equiv 1\pmod m\): \(x\bmod m\) is an inverse of \(a\) modulo \(m\). Extended Euclid is the standard constructive method.

Worked examples

Example 1 — Euclid on \((252,198)\). \[ \begin{align*} 252 &= 1\cdot 198 + 54,\\ 198 &= 3\cdot 54 + 36,\\ 54 &= 1\cdot 36 + 18,\\ 36 &= 2\cdot 18 + 0. \end{align*} \] So \(\gcd(252,198)=18\). Invariant: \(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=\gcd(18,0)=18\).

Example 2 — Extended: \(252x+198y=18\). \[ \begin{align*} 18 &= 54 - 1\cdot 36,\\ 36 &= 198 - 3\cdot 54 \implies 18 = 4\cdot 54 - 1\cdot 198,\\ 54 &= 252 - 1\cdot 198 \implies 18 = 4\cdot 252 - 5\cdot 198. \end{align*} \] Check: \(252\cdot 4 + 198\cdot(-5)=1008-990=18\).

Example 3 — Tabular extended Euclid for \(\gcd(240,46)\).

\(r\) \(q\) \(s\) \(t\)
\(240\) \(1\) \(0\)
\(46\) \(0\) \(1\)
\(10\) \(5\) \(1\) \(-5\)
\(6\) \(4\) \(-4\) \(21\)
\(4\) \(1\) \(5\) \(-26\)
\(2\) \(1\) \(-9\) \(47\)
\(0\) \(2\) stop

\(\gcd=2=240\cdot(-9)+46\cdot 47\). Check: \(-2160+2162=2\).

Example 4 — Diophantine equation.
Solve \(240x+46y=10\). \(\gcd=2\mid 10\). From \(240(-9)+46(47)=2\), multiply by \(5\): \(240(-45)+46(235)=10\). General: \[ x=-45+23k,\qquad y=235-120k,\quad k\in\mathbb{Z}. \]

Example 5 — No solution.
\(15x+25y=7\): \(\gcd=5\nmid 7\), impossible.

Example 6 — Inverse preview.
\(\gcd(7,26)=1\). Euclid: \(26=3\cdot7+5\), \(7=1\cdot5+2\), \(5=2\cdot2+1\), \(2=2\cdot1+0\). Back-sub: \[ 1=5-2\cdot2,\quad 2=7-5\Rightarrow 1=3\cdot5-2\cdot7,\quad 5=26-3\cdot7\Rightarrow 1=3\cdot26-11\cdot7. \] Inverse of \(7\) mod \(26\) is \(-11\equiv 15\). Check: \(7\cdot 15=105=4\cdot26+1\).

Example 7 — Fibonacci worst case.
\(F_8=21\), \(F_7=13\): \(21=1\cdot13+8\), \(13=1\cdot8+5\), \(8=1\cdot5+3\), \(5=1\cdot3+2\), \(3=1\cdot2+1\), \(2=2\cdot1+0\). Many steps for small inputs — the pattern of all quotients \(1\) is the slow case.

Example 8 — Prove \(\gcd(ca,cb)=|c|\gcd(a,b)\) for \(c\neq 0\).
By FTA, or: if \(d=\gcd(a,b)\) and \(ax+by=d\), then \(cax+cby=cd\), so \(\gcd(ca,cb)\mid |c|d\) wait — more carefully: common divisors of \(ca,cb\) are \(|c|\) times common divisors of \(a,b\) when carefully tracking signs. Using FTA is cleanest for this volume after Day 71.

Exercises

A. Plain Euclid

  1. Compute \(\gcd(1071,462)\) by Euclid; show every remainder step.
  2. Compute \(\gcd(12345,678)\).
  3. Compute \(\gcd(91,0)\) and \(\gcd(0,91)\).
  4. Prove carefully: \(\gcd(a,b)=\gcd(b,a-b)\) when \(a\ge b\ge 0\).
  5. Trace Euclid on \((F_{10},F_9)\). Count division steps.
  6. Run Euclid on \((100,35)\) and list the invariant gcd at each line.

B. Extended Euclid

  1. Find integers \(x,y\) with \(1071x+462y=\gcd(1071,462)\).
  2. Find Bézout coefficients for \((240,46)\) by back-substitution and confirm the table.
  3. Find \(x,y\) with \(17x+13y=1\). Then find the inverse of \(17\) modulo \(13\) and of \(13\) modulo \(17\).
  4. For \(a=99\), \(b=78\), compute \(d=\gcd\) and \(x,y\) with \(ax+by=d\).
  5. Show two different Bézout pairs for \(\gcd(15,25)=5\).
  6. Tabular extended Euclid for \((123,45)\).

C. Diophantine equations

  1. Determine whether \(14x+35y=21\) has integer solutions; if so, find the general solution.
  2. Same for \(14x+35y=20\).
  3. Find all positive integer solutions (if any) to \(6x+9y=21\) with \(x,y>0\).
  4. Prove: if \(ax+by=c\) is solvable and \(ab\neq 0\), then it has infinitely many solutions.
  5. Freight problem: “apples cost 6, oranges 10; total cost 44.” Cast as Diophantine; solve nonnegatively if possible.

D. Theory and proofs

  1. Prove that every common divisor of \(a\) and \(b\) divides \(\gcd(a,b)\), using Bézout.
  2. Prove Euclid’s lemma using Bézout: if \(p\) prime, \(p\mid ab\), \(p\nmid a\), then \(p\mid b\).
  3. Prove: \(\gcd(ca,cb)=|c|\gcd(a,b)\) for \(c\neq 0\).
  4. Prove that \(I=\{ax+by\}\) has least positive element equal to \(\gcd(a,b)\) (fill every gap in the proof above).
  5. CS literacy: explain why extended Euclid is the right tool to solve \(ax\equiv 1\pmod m\) when \(\gcd(a,m)=1\) (prose, no code).

E. Stretch

  1. Binary GCD idea (Stein): both even ⇒ factor \(2\); one even ⇒ drop \(2\) from that one; both odd ⇒ replace larger by \(|a-b|\). Hand-compute \(\gcd(48,18)\).
  2. How many steps does Euclid take on \((F_{12},F_{11})\)? Estimate via Lamé.
  3. Prove: the number of steps of Euclid on \((a,b)\) with \(a>b\ge 1\) is at most \(1+\log_\varphi(\sqrt{5}b)\) roughly — write a clean inequality from \(b\ge F_{k+1}\).
  4. Solve \(17x\equiv 1\pmod{100}\) by extended Euclid.

Deep dive — invariant as a correctness template

Think of Euclid as a loop with state \((a,b)\):

// mathematical pseudocode — not a lab
assert not both zero
while b ≠ 0:
    // invariant: gcd(a,b) equals original gcd
    (a,b) ← (b, a mod b)
return a

Loop invariant proof pattern (reusable in CS literacy):

  1. Initialization: invariant holds on entry.
  2. Maintenance: gcd recurrence preserves it.
  3. Termination: second coordinate is a strictly decreasing nonnegative integer.
  4. Exit: \(b=0\) ⇒ return \(a=\gcd(a,0)\).

Deep dive — complexity more carefully

Lamé (quantitative). If Euclid takes \(N\) divisions on \(a>b\ge 1\), then \(b\ge F_{N+1}\). Step count is \(O(\log b)\).

Why Fibonacci is worst. Quotients all equal to \(1\) minimize the drop: remainders follow a Fibonacci-like recurrence. Any quotient \(\ge 2\) shrinks faster.

Bit cost literacy. Schoolbook division of \(O(\log n)\)-bit integers is not \(O(1)\); total classical bit complexity of gcd is still far better than trial division up to \(b\). For this volume, \(O(\log n)\) steps is the required takeaway.

Deep dive — all solutions to \(ax+by=c\)

Once \(ax_0+by_0=d\) and \(d\mid c\), set \(x^*=x_0(c/d)\), \(y^*=y_0(c/d)\).
If \((x,y)\) is another solution, \(a(x-x^*)+b(y-y^*)=0\). Dividing by \(d\) and using \(\gcd(a/d,b/d)=1\) yields \[ x=x^*+(b/d)k,\qquad y=y^*-(a/d)k. \] Nonnegative solutions: restrict \(k\) so \(x,y\ge 0\) when \(a,b>0\) — typically a finite interval of \(k\).

Additional worked examples

Example 9 — \(\gcd(a,b)=\gcd(a,b+ka)\).
Common divisors match because \(b=(b+ka)-ka\).

Example 10 — Inverse of \(43\) mod \(100\).
\(100=2\cdot 43+14\), \(43=3\cdot 14+1\).
\(1=43-3\cdot 14=43-3(100-2\cdot 43)=7\cdot 43-3\cdot 100\).
Inverse \(\equiv 7\). Check: \(43\cdot 7=301\equiv 1\pmod{100}\).

Example 11 — Nonnegative Diophantine.
\(6x+9y=21\): \(d=3\mid 21\). From \(6(-1)+9(1)=3\), scale by \(7\): \(6(-7)+9(7)=21\).
General: \(x=-7+3k\), \(y=7-2k\). Nonnegative forces \(k=3\): \((x,y)=(2,1)\).

Example 12 — Fibonacci pair.
\((F_7,F_6)=(13,8)\): remainders \(5,3,2,1,0\) — many steps for small inputs.

Example 13 — Prove every common divisor divides the gcd via Bézout.
\(d=ax+by\) ⇒ any common divisor divides the right-hand side, hence divides \(d\).

More exercises

  1. Run tabular extended Euclid on \((321,123)\).
  2. Find all nonnegative solutions to \(4x+6y=20\).
  3. Prove: if \(ax+by=1\) then \(\gcd(a,b)=1\).
  4. CS literacy paragraph: why gcd speed matters for RSA keygen hygiene (reject bad primes) as an idea only.
  5. Compare number of steps of Euclid on \((89,55)\) vs \((90,54)\).
  6. Solve \(19x\equiv 1\pmod{100}\) by extended Euclid.

Selected mini-solutions

  1. \(1071=2\cdot 462+147\); \(462=3\cdot 147+21\); \(147=7\cdot 21\) ⇒ \(\gcd=21\).
  2. Inverse of \(43\) mod \(100\) is \(7\) (Example 10).
  3. Bézout: common divisors divide \(d\).
  4. Extended Euclid on \((17,100)\) (Day 74 style) yields inverse \(53\).

Common pitfalls

Pitfall Fix
Sign errors in back-substitution Check \(ax+by=d\) numerically every time
Stopping when remainder is \(1\) without coefficients Extended form needs the full chain
Claiming \(ax+by=c\) always solvable Need \(d\mid c\)
Using \(\gcd\) of negatives inconsistently Reduce to nonnegative inputs
Off-by-one in general solution \(\pm(b/d)k\) Derive once; stick to one convention
Confusing steps with bit operations \(O(\log n)\) steps is the right literacy level here
Forgetting to scale Bézout when \(c\neq d\) Multiply coefficients by \(c/d\)

Checkpoint

  • Can run Euclid and prove \(\gcd(a,b)=\gcd(b,a\bmod b)\)
  • Can explain termination + invariant correctness
  • Can state Fibonacci worst-case intuition and \(O(\log n)\)
  • Can produce Bézout coefficients by back-substitution or table
  • Can decide solvability of \(ax+by=c\) and write the general solution
  • Can prove Euclid’s lemma via Bézout
  • Exercises A–D done

Two personal takeaways:

  1. …
  2. …

Tomorrow

Day 73 — Modular arithmetic (congruences and operations).