Project · Implement and verify the extended Euclidean algorithm

project

hard

module project

Ship something real. Submit your work when you're done.

Brief

Implement `xgcd(a, b)` from scratch, returning a triple `(g, s, t)` with $a \cdot s + b \cdot t = g = \gcd(a, b)$. Verify Bézout's identity holds on at least 30 input pairs covering positive, negative, zero, coprime, and large random cases. Then use your implementation to solve the linear Diophantine equation $847 x + 609 y = \gcd(847, 609)$, finding both a particular solution and the general family of solutions. The deliverable is a working library plus a write-up that convinces a sceptical reader your implementation is correct on every edge case.

Deliverables

A Python module `xgcd.py` implementing `xgcd(a, b)` with no use of `math.gcd` or any sympy helper — only `divmod` and basic arithmetic.
A test script that runs `xgcd` on at least 30 input pairs (including $(0, 0), (0, 5), (5, 0), (-12, 18), (1071, 462)$, ten random small pairs, and ten random pairs with absolute values $\geq 10^9$) and asserts $a s + b t = g$ and $g = |\gcd|$ in every case.
A short write-up (Markdown or PDF) that traces `xgcd(847, 609)` step by step, shows the Bézout coefficients $(s, t)$, and writes the general solution to $847 x + 609 y = \gcd(847, 609)$ in the form $(x, y) = (x_0 + k \cdot 609/g, \ y_0 - k \cdot 847/g)$ for $k \in \mathbb{Z}$.
A note on edge cases: explain how your code handles $a = 0$, $b = 0$, both zero, and negative inputs, and why the resulting $g$ is non-negative.

How we grade it

On 30+ test pairs (including all listed edge cases), `a * s + b * t == g` holds exactly — checked by `assert`, not 'looks right'.
The output `g` matches `math.gcd(a, b)` (which is non-negative) on every test pair, including pairs with negative inputs.
The trace of `xgcd(847, 609)` shows every iteration's $(q, r, s, t)$ tuple — the reader can re-derive the answer line by line without running the code.
The general solution to $847 x + 609 y = g$ is written explicitly with the correct coefficients $b/g$ and $a/g$ on the family parameter, *and* a particular solution $(x_0, y_0)$ is given.
The implementation uses only `divmod` (or `//` and `%`) and never calls a library gcd — it's a from-scratch extended Euclidean.

Hints

Maintain three running pairs in lock-step:

(r_{\text{old}}, r), (s_{\text{old}}, s), (t_{\text{old}}, t)

, initialised to

(a, b), (1, 0), (0, 1)

. The loop invariant

a \cdot s_i + b \cdot t_i = r_i

must hold every iteration.

The update at each step is

(r_{\text{old}}, r) \leftarrow (r, r_{\text{old}} - q \cdot r)

, where , and the same pattern for and . Don't write the update with destructive single-variable assignments — use tuple unpacking, or you'll clobber the values you still need.

Edge cases: if

a = 0

and

b = 0

, return

(0, 0, 0)

(or

(0, 1, 0)

— pick a convention and document it). If exactly one is 0, the answer is straightforward — work it out from the loop invariant.

For negative inputs, the easiest correct approach is to work with

|a|, |b|

and then flip the signs of

s, t

as needed at the end. Verify the Bézout equation against the original signed inputs, not the absolute values.

When you generate the 30 test pairs, include some where

a < b

, some where

a > b

, and some where one is a multiple of the other — those last cases terminate in one step.

Expected output

A test run that ends with something like:

xgcd(0, 0) -> g=0, s=0, t=0 xgcd(0, 5) -> g=5, s=0, t=1 verify: 0*0 + 5*1 = 5 OK xgcd(5, 0) -> g=5, s=1, t=0 verify: 5*1 + 0*0 = 5 OK xgcd(-12, 18) -> g=6, s=-1, t=-1 verify: -12*-1 + 18*-1 = 12 - 18 = -6 ... fix sign convention xgcd(1071, 462) -> g=21, s=-3, t=7 verify: 1071*-3 + 462*7 = 21 OK xgcd(847, 609) -> g=7, s=...,t=... verify: 847*s + 609*t = 7 OK ... 24 more ... All 30 tests passed.

…followed by a Markdown section reading roughly:

gcd(847, 609) = 7. Bézout: 847 * (-5) + 609 * 7 = -4235 + 4263 = 28 ... (work out actual coefficients) Particular solution to 847x + 609y = 7: (x0, y0) = (s, t) from xgcd. General solution: (x, y) = (x0 + k * 609/7, y0 - k * 847/7) = (x0 + 87k, y0 - 121k), k in Z.

Stretch goals

Implement a recursive version xgcd_rec(a, b) that returns the same triple, and verify it agrees with the iterative version on all 30 test pairs. The recursion is: if

b = 0

return

(a, 1, 0)

; else recurse on

(b, a \bmod b)

and reconstruct.

Use your xgcd to compute the modular inverse of 17 modulo (a prime commonly used in competitive programming and hash-table seeding). Verify .