Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 19m 33s17 days 22 hours 19 minutes 33 seconds.

Advanced - Number Theory · 4:06

Extended Euclidean Algorithm

Euclid's algorithm finds gcd(a, b); the extended version also finds integers x and y with a·x + b·y = gcd(a, b). We run Euclid down on (55, 80) keeping the quotients, carry the coefficients back up from (1, 0) to get 55·3 + 80·(−2) = 5, unroll the recursion into a loop with two invariants, and use it to compute modular inverses for any modulus, where Fermat's shortcut fails.

You will learn

State Bézout's identity and compute x, y with a·x + b·y = gcd(a, b) by back-substitution
Derive the update x = y1, y = x1 − q·y1 from a mod b = a − q·b
Write the iterative extended Euclid and explain its two invariants; handle negative inputs and overflow
Compute modular inverses for any modulus, and explain when an inverse exists and why a^(m−2) only works for prime m

Chapters

PreviousMatrix Exponentiation and Fibonacci NextLinear Diophantine Equations