GCD and Extended Euclid
In short: Euclid's algorithm replaces (a, b) with (b, a % b) until b is 0,
because both pairs share the same common divisors, and that pair shrinks fast enough to
finish in O(log min(a, b)) time and O(1) space. Run the same replacement on two tracked
coefficients (extended Euclid) and you get Bézout's identity a·x + b·y = gcd(a, b) for
free, which gives a's modular inverse whenever gcd(a, m) = 1 — exactly the tool for
undoing a multiply modulo m.
Quarry shows record ids to the outside world in URLs and API responses. Sequential ids leak information. If yesterday's record was 1,000 and today's is 1,850, anyone can see how fast your data is growing. The usual cure is to scramble each id before showing it. Multiply it by a secret key modulo 2³², which in a 32-bit word is just "multiply and let it wrap":
The public ids look random. But Quarry needs the real id back when a URL comes in, so it
has to undo a multiplication modulo 2³². That needs a number INV with
KEY · INV ≡ 1 (mod 2³²), the key's modular inverse. The algorithm that finds it is
more than two thousand years old and still runs in O(log m) steps. It also answers
whether an inverse exists at all.
Euclid's algorithm
The greatest common divisor gcd(a, b) is the largest number dividing both.
Euclid's observation: any number that divides both a and b also divides
a − q·b for any q, and in particular a % b. So the pairs (a, b) and (b, a % b)
have exactly the same common divisors. Keep replacing the pair until the second
number is 0. The first number is then the gcd:
a, b, steps = 1234, 322, 0
while b:
a, b = b, a % b
steps += 1
print(a, steps)Why so few steps? After two iterations the larger number has at least halved: if
b ≤ a/2 then a % b < b ≤ a/2, and otherwise a % b = a − b < a/2. So the loop is
O(log min(a, b)). The worst case is two consecutive Fibonacci numbers, where every
quotient is 1 and the numbers shrink as slowly as possible. Even then it takes only
about log base φ of n steps, where φ ≈ 1.618:
| digits in n | worst-case steps |
|---|---|
| 5 | 24 |
| 10 | 48 |
| 20 | 96 |
| 21 | 100.5 |
Each extra decimal digit costs fewer than 5 more steps, so numbers up to 20 digits never need more than 100. Quarry's 32-bit keys have at most 10 digits, so the loop never runs more than about 48 times.
Extended Euclid: keeping the receipts
Every remainder Euclid produces is a combination of the two original numbers. It
starts with a = 1·a + 0·b and b = 0·a + 1·b, and each new remainder is
"two rows up minus q times one row up". So if you apply the same rule to the
coefficients, you always know how to write the current remainder as a·x + b·y.
When the remainder reaches the gcd, you have Bézout's identity:
a·x + b·y = gcd(a, b).
Step through a = 60, b = 17. The arrows show the two cells each new value is built
from, and every row satisfies 60·x + 17·y = r:
Every row keeps the promise 60·x + 17·y = r. When r reaches the gcd, x and y are the Bézout coefficients, and y is 17's inverse mod 60.
The first two rows say 60 = 60·1 + 17·0 and 17 = 60·0 + 17·1. 6 by 4 table. At row 1, column 1 — value 17. 6 of 24 cells filled.
In code you only need the last two rows at any moment:
Modular inverses
a·x ≡ 1 (mod m) means a·x + m·y = 1 for some whole number y, which is Bézout's
identity with gcd 1. So:
- An inverse exists exactly when
gcd(a, m) = 1. If somed > 1divides both, everya·x + m·yis a multiple ofdand can never equal 1. - Extended Euclid finds it. Run it on
(a, m)and take the coefficient ofa, reduced into0 … m − 1.
For the scrambler the modulus is 2³², whose only prime factor is 2. So a key has an inverse exactly when it's odd. Quarry's key is odd, and its inverse unscrambles every id:
When the modulus is prime there's a second route, Fermat's little theorem, which
says a**(p-1) ≡ 1 (mod p) for a not divisible by p. So a**(p-2) is the inverse,
and last lesson's mod_pow computes it. That doesn't work for 2³², which isn't prime.
Extended Euclid works for any modulus.
print(pow(6, -1, 35), 6 * pow(6, -1, 35) % 35)The coefficient extended Euclid returns can be negative. Forget to fix that and a "key" of −7 goes into the scrambler:
It prints -7 1. −7 is a correct inverse mathematically, but a scrambler key has to be a number between 0 and m − 1.
Now run the table-builder yourself. Each frame adds one row of [q, r, x, y]. Try
(35, 6), then a pair with a common factor such as (84, 36), and watch the last
non-zero r become the gcd:
Your extended Euclid, one row per division. Every row satisfies a·x + b·y = r.
Interview corner — which offsets can the clock reach?
Quarry's replay tool can move a log cursor forward by a entries or back by b
entries, as many times as you like in any order. Starting from entry 0, can it land
exactly on entry t? Every sequence of moves reaches a·i − b·j for some counts, and
by Bézout those are exactly the multiples of gcd(a, b). So the answer is a single test:
Brute-force searching over move sequences would never be sure when to stop. Bézout
answers it immediately, and extended Euclid even gives the counts i and j.
Quick practice
a, b = 48, 18
while b:
a, b = b, a % b
print(a)ZeroDivisionErrorIt crashes instead of returning 6. Swap which variable the while condition watches.
🎯 Your turn
Write mod_inverse(a, m) using extended Euclid, without pow(a, -1, m). Return the
x in 0 … m − 1 with a·x % m == 1, or None if a has no inverse mod m
(because gcd(a, m) != 1). m >= 2.
mod_inverse(17, 60)→53mod_inverse(6, 9)→None, since both are divisible by 3
Hint — run extended Euclid on (a, m), tracking only the coefficient of a. If the
final remainder isn't 1, return None. Otherwise return that coefficient % m.
Then press ▶ Run, try the Live App chips, and hit ✓ Check. ✅