How does the extended Euclidean algorithm turn gcd(a, n) = 1 into an actual inverse of a modulo n?
answer
- one more column per step
- how each remainder is built
- a*x + n*y = gcd(a, n)
- the n*y term vanishes modulo n
- take x, the coefficient of a
basics
~20 sIt returns integers x and y with ax + ny = gcd(a, n), by carrying those two coefficients alongside the remainders. When the gcd is 1, reducing modulo n drops the n*y term, so x is the inverse of a.
solid answer
~50 sAlongside each remainder, the algorithm carries how that remainder is built out of the two starting values - Bezout's identity, `a*x + n*y = gcd(a, n)`. Every remainder is a whole-number combination of `a` and `n`, so the coefficients update with the same subtraction the remainders do: if `r_new = r_old - q*r`, then the coefficients follow `x_new = x_old - q*x`. When the sequence ends, the surviving remainder is the gcd and its coefficients satisfy the identity. If that gcd is 1, read the identity modulo `n`: `n*y` is a multiple of the modulus and disappears, leaving `a*x = 1 (mod n)`. Only the `x` column is needed for an inverse, so implementations usually drop `y`. The returned `x` may be negative - for `a = 3, n = 7` it comes back as `-2` - so it is shifted into the residue range, giving 5.
code
pseudocode · 15 linesextended_gcd(a, n):
old_r, r = a, n
old_x, x = 1, 0 // coefficient of a for each remainder
while r != 0:
q = old_r div r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
// old_r = gcd(a, n) and a * old_x + n * (something) = old_r
return old_r, old_x
inverse(a, n):
g, x = extended_gcd(a, n)
if g != 1:
return NONE // a and n share a factor
return ((x mod n) + n) mod n // x may be negativego deeper
Know what comes back: the gcd plus coefficients satisfying ax + ny = gcd. When that gcd is 1, the coefficient of a is the inverse once shifted into the residue range.
Explain the bookkeeping: each remainder is an integer combination of the two starting values, and the coefficients update with exactly the same subtraction the remainders do.
Show the guard rails in real code - check the gcd before trusting the coefficient, normalise a possibly negative coefficient, and prefer this route because it works against any modulus.
Frame it as the general primitive: one routine covers inverses, linear congruences and Diophantine questions for any modulus, so specialised alternatives need a measured reason to exist.
## The identity the algorithm is really computing **Bezout's identity** states that for any integers `a` and `n` there exist integers `x` and `y` with `a*x + n*y = gcd(a, n)` The **extended Euclidean algorithm** is the constructive proof: it produces a concrete `x` and `y`, not merely the promise that they exist. That construction is what converts "these are coprime" into a usable inverse, because if the gcd is 1 then reducing the identity modulo `n` removes the `n*y` term and leaves `a*x = 1 (mod n)`. ## Carrying the coefficients along the remainders The ordinary gcd computation replaces a pair of values with a smaller pair until one of them reaches zero. The extension adds bookkeeping: for each remainder in that sequence, keep **how it is built from the original `a` and `n`**. The key observation is that the bookkeeping obeys the same rule as the values: - Every remainder is an integer combination `a*x + n*y` of the two starting values. The first two trivially are: `a = a*1 + n*0` and `n = a*0 + n*1`. - Each step forms a new remainder as `r_new = r_old - q*r`, where `q` is the quotient. - Substituting the combinations for `r_old` and `r` shows the new combination is `x_new = x_old - q*x` and `y_new = y_old - q*y` - **the coefficients update with the same subtraction**. So the extension costs one or two extra columns of arithmetic per step and nothing else. Since only the coefficient of `a` is needed to read off an inverse, implementations that want just the inverse track a single extra column. ## A worked run: a = 3, n = 7 | iteration | quotient q | (old_r, r) | (old_x, x) | |---|---|---|---| | start | - | (3, 7) | (1, 0) | | 1 | 0 | (7, 3) | (0, 1) | | 2 | 2 | (3, 1) | (1, -2) | | 3 | 3 | (1, 0) | (-2, 7) | The loop stops when `r` hits 0, and the surviving `old_r` is `gcd(3, 7) = 1` with coefficient `old_x = -2`. Checking the identity: `3*(-2) + 7*1 = 1`. Reduced into the residue range, `-2` becomes `5`, and `3 * 5 = 15 = 14 + 1 = 1 (mod 7)`. The inverse of 3 modulo 7 is 5. Note the first iteration when `a < n`: the quotient is 0 and the step simply swaps the pair, costing one cheap round rather than needing a special case. ## Reading the result correctly Three things have to be done with the returned values, and each is a place where implementations go wrong: 1. **Check the gcd before using the coefficient.** If the algorithm returns a gcd other than 1, there is no inverse and the coefficient is meaningless as one. It still satisfies the identity - just for the gcd, not for 1. 2. **Take the coefficient of `a`, not of `n`.** The other coefficient records how many multiples of the modulus were absorbed; it plays no part in the inverse. 3. **Shift the coefficient into the residue range.** The identity holds over the integers, so the coefficient can land outside `0..n-1` on either side, and it is brought back into range before being returned. ## What it gives you that the plain gcd does not | you want | plain gcd | extended version | |---|---|---| | does an inverse exist? | yes, gcd = 1 answers it | yes | | the inverse itself | no | yes, the coefficient of `a` | | solving a linear congruence | no | yes, via the same coefficients | | modulus must be prime | - | no, works for any modulus | That last row is the practical reason this is the general tool: unlike routes that lean on a prime modulus, the extended Euclidean algorithm inverts against **any** modulus, and when no inverse exists it says so instead of returning a wrong answer. ## Common misreadings - **Taking the gcd itself as the inverse.** The gcd is the right-hand side of the identity; the inverse is a coefficient on the left. - **Assuming the coefficient is already a valid residue.** It is an integer, frequently negative, and needs to be brought into range. - **Skipping the gcd check.** Using the coefficient when the gcd is greater than 1 produces a value that satisfies nothing, silently. - **Believing the extension changes the cost.** The remainder sequence is the same one; only a small constant of extra bookkeeping is added per step.
- The algorithm returns the coefficient -2 for a = 3, n = 7. Is that a usable inverse?Yes. The identity holds over the integers, so coefficients come out signed: 3*(-2) + 7*1 = 1. Modulo 7, -2 is the same element as 5, and 3 * 5 = 15 = 1 (mod 7). Implementations shift the coefficient into 0..n-1 before returning it so callers get a residue rather than a signed integer.
- What does the second Bezout coefficient, the one multiplying n, actually tell you?It records how many multiples of the modulus the identity absorbs - it certifies that a*x and the gcd differ by exactly that multiple of n. It is never needed to read off an inverse, because that term vanishes the moment the identity is reduced modulo n, which is why an inverse routine can track one coefficient column instead of two.
- The algorithm returns gcd = 4. What should the calling code do?Treat it as 'no inverse' and take the other branch. The returned coefficient still satisfies a*x + n*y = 4, but nothing in that makes it behave like an inverse; multiplying by it does not undo multiplication by a. Any code that uses the coefficient without checking the gcd first produces a silently wrong value.
saying these in an interview costs you the question
- Returns the gcd itself as the inverse
- Uses the coefficient without checking the gcd is 1
- Assumes the coefficient is already inside 0..n-1
- Picks the coefficient of n instead of the coefficient of a
- Thinks the extension needs a prime modulus to work