Remainders can carry a proof with them
Finding a greatest common divisor is only the beginning. The same remainder computation can produce integers that certify the answer, show whether modular division is possible, and construct a number satisfying two congruences. The useful connection is an invariant: each remainder stays an integer linear combination of the original inputs.
We first work with nonnegative integers , not both zero. Arithmetic in the algorithms below is exact integer arithmetic. When a modular problem later has a negative coefficient, we will normalize it before calling this nonnegative-input algorithm.
Why replacing a pair by a remainder preserves its gcd
Definition 11.1.1
(Gcd and Euclidean division)
The greatest common divisor is the greatest positive integer dividing both inputs. If , Euclidean division gives unique integers such that and .
A positive integer divides both exactly when it divides both . In one direction, a divisor of divides their integer linear combination . In the other, a divisor of divides . Thus the two pairs have precisely the same common divisors, and
Repeatedly make this replacement. The second component is a nonnegative integer that strictly decreases whenever it is positive, so the process terminates. At a pair , the gcd is , because the positive divisors common to and 0 are exactly the divisors of . The not-both-zero assumption ensures that this final is positive.
Extend the loop to retain linear combinations
Track coefficient pairs for both current remainders. Initially and . If the current pair has representations and , then its next remainder is
The coefficient update is therefore forced by the remainder update; it is not a separate guess about the final answer.
EXTENDED_GCD(a, b):
require a >= 0, b >= 0, and a + b > 0
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
old_t, t = t, old_t - q * t
return old_r, old_s, old_t
Each comma assignment is simultaneous: its right-hand side uses the
old values of that pair. In particular, overwriting old_r before
computing the next remainder would lose the value that must be divided.
The quotient // is exact floor division on the nonnegative inputs
present at that iteration, not floating-point division followed by rounding.
Theorem 11.1.2
(Extended Euclid returns a Bézout certificate)
The algorithm terminates and returns integers satisfying
Proof
(Preserve both the divisor set and the coefficient equations)
At every loop entry, the invariant is
Initialization gives the identity representations. Euclidean replacement preserves the common divisors, while subtracting times one representation from the other gives exactly the two coefficient updates. The new second remainder is smaller than the old positive one, so termination follows as before.
At termination, r is 0 and old_r is the positive gcd. The other
invariant equation gives the returned Bézout identity. This proof also
covers , when the loop never runs, and , when the first
quotient is 0 and the next pair is .
Worked example 11.1.3
(Carry coefficients through gcd(240,46))
Start with remainders 240 and 46, represented by coefficient pairs and . Each row gives a newly generated remainder:
| Quotient | New remainder | Coefficient of 240 | Coefficient of 46 |
|---|---|---|---|
| 5 | 10 | 1 | −5 |
| 4 | 6 | −4 | 21 |
| 1 | 4 | 5 | −26 |
| 1 | 2 | −9 | 47 |
| 2 | 0 | 23 | −120 |
The last nonzero remainder is 2, and its row gives . Check the identity directly: . The coefficient row for the zero remainder is a true identity too, but it is not the row returned as the gcd certificate.
What an independently checked certificate must establish
Suppose somebody supplies positive and coefficients claiming that . Check both that divides and that . The divisibility check shows is a common divisor. The identity shows every common divisor divides , since it divides every integer linear combination of . No larger positive common divisor is then possible.
Counterexample mode
An integer linear combination alone is not a gcd certificate
For 18 and 30, the true identity does not make 12 their gcd: 12 does not divide either input. Their gcd is 6.
An identity of the special form does prove coprimality, because 1 is automatically a positive common divisor of all integers. For a general positive claimed gcd, do not omit the common-divisor check.
Proof X-ray
Counting divisions is not counting bit operations
Assume first that . If , the first division already terminates the loop. Otherwise consider a positive remainder pair : if , the next remainder is already smaller than . If , the quotient is 1 and the next remainder is smaller than . Thus within at most two replacements the larger current remainder is at most half its earlier value, or the loop has already terminated.
After the first division, the remainders are at most , so the number of divisions is . An initially reversed input order costs at most one extra quotient-0 exchange. Inputs with a zero component terminate immediately or after that exchange.
This counts arithmetic steps. Dividing or multiplying large integers is not a constant-cost bit operation, and extended Euclid also updates possibly large coefficients. A full bit-time analysis must charge for those operations; the logarithmic division count alone is not that analysis.
Modular division means finding an inverse
Definition 11.1.4
(Congruence and modular inverse)
Write when divides . In the rest of the note . An inverse of modulo is an integer such that .
Theorem 11.1.5
(Exactly the coprime coefficients are invertible)
An integer has an inverse modulo if and only if . When it exists, the inverse is unique modulo .
Proof
(Read an inverse from Bézout, and reverse the reasoning)
First replace by its least nonnegative residue . The pairs and have the same common divisors, and for every integer .
If extended Euclid gives , reduction modulo gives , so is an inverse. Conversely, an inverse gives for some integer . Every common divisor of divides 1, hence the gcd is 1.
If are both inverses, then . Multiplying by one inverse gives ; this proves uniqueness of the residue class, not uniqueness as an integer.
For example, , , and . Substituting backwards gives . The inverse of 17 modulo 43 is therefore ; indeed .
Ordinary integer division is not a substitute. A fraction such as becomes modular multiplication by only when that inverse exists. For instance, 2 is not invertible modulo 6.
Concept lensAlgebraic
The gcd as the generator of all combinations
Consider the set of all integer combinations . If , every combination is a multiple of , and extended Euclid exhibits itself as a combination, so the set is exactly . Then is invertible modulo exactly when is a combination, that is, when this set is all of and . For and the set is , which misses .
Common mistake
(Feeding a negative coefficient to the nonnegative loop)
Extended Euclid is stated for nonnegative inputs. Running it directly on and makes the quotients and remainders depend on how a language rounds signed division, and the proof above no longer describes what the code computes. Reduce first: , then run the loop on and .
A noninvertible coefficient can still give solutions
Theorem 11.1.6
(Solve a linear congruence by reducing its gcd)
For integers and , put . The congruence is solvable exactly when . If solvable, it has exactly distinct residue classes modulo .
Necessity follows because implies . For sufficiency, suppose and divide the full integer equation, including the modulus, by . Set , , . Then
If , the reduced coefficient is coprime to , so its inverse gives one residue modulo . The solutions modulo are
These classes are distinct: divides only if divides . They exhaust the solutions because every solution is congruent to modulo . If , the reduced congruence places no restriction at all. Here , and all residue classes are solutions; no inverse modulo 1 is needed.
Common mistake
(Dividing a congruence without dividing its modulus)
Dividing the coefficient and right-hand side without changing the modulus is generally wrong. For , the correct reduction is , giving both 1 and 4 modulo 6. Keeping modulus 6 would incorrectly discard the class 4.
Worked example 11.1.7
(A congruence with several solution classes)
Solve . Here , which divides 9, so there are exactly three classes. Divide everything, including the modulus: . The inverse of 2 modulo 5 is 3, so . The solutions modulo 15 are for , that is . Check: , , and . By contrast has no solution, because .
Construct a Chinese-remainder solution instead of guessing
Consider and , where . Write to satisfy the first congruence. The second becomes . With , the preceding theorem proves that a solution exists if and only if .
When compatible and , extended Euclid finds an inverse of modulo . Solve
If , take : compatibility already makes every such satisfy the second congruence. The answer is unique modulo . Indeed, two answers differ by a multiple of both moduli, hence by a multiple of their least common multiple. Conversely, adding that least common multiple preserves both congruences. Equivalently, changing by changes by .
Worked example 11.1.8
(Solve two coprime congruences constructively)
Find and . Put , so . The inverse of 5 modulo 7 is 3, since . Thus and .
Direct checking gives . The residue class modulo 35 represents all integer solutions, not just the displayed one.
Common mistake
(Multiplying the moduli when they share a factor)
The moduli need not be coprime, but compatibility then matters. The two-modulus derivation gives both the compatibility test and the correct combined modulus. Multiplying the moduli indiscriminately would miss the smaller true period when their gcd exceeds 1.
Solved exercises
Quick check
(Run extended Euclid on 99 and 78. Give the remainder sequence and a Bézout identity for the gcd. What checks certify the answer independently?)
Keep a coefficient pair beside every remainder.
Solution · Answer
The divisions are , , , , and . The successive coefficient pairs for 21,15,6,3 are , , , . Thus . Check that 3 divides both inputs and that . The first check makes 3 a common divisor; the identity makes every common divisor divide 3. Together they certify the gcd.
Quick check
(Find the inverse of modulo 26. Keep the call to extended Euclid within its nonnegative-input contract and check the final answer using the original negative coefficient.)
Reduce to a nonnegative residue first.
Solution · Answer
Normalize . The divisions , , , give . Hence the inverse is 11. Using the original coefficient, , so the check succeeds. There is no need to run the supplied loop on negative remainders or assume a programming language's signed-division rules.
Quick check
(Solve , and decide whether replacing 30 by 31 leaves any solution. Also solve and .)
Compute the gcd of the coefficient and the modulus first.
Solution · Answer
The gcd is 2, which divides 30. Reduce to . Since , we get . The two classes modulo 100 are 45 and 95; substitution gives remainder 30 for both. The right-hand side 31 is not divisible by 2, so there is no solution.
For , the gcd is 3 and the reduced modulus is 1: all three classes 0,1,2 work. For , the gcd does not divide the right-hand side, so no class works.
Quick check
(Solve , . What changes if the second residue is 4? Give the correct period of the compatible solution.)
Find the gcd of the moduli and test whether it divides the difference of the residues.
Solution · Answer
The gcd is 3 and is divisible by 3, so the first system is compatible. Write , giving and hence . Thus and . The period is , not 54. Indeed 14 has remainders 2 and 5 as required.
With second residue 4, the difference is , not divisible by 3, so the system is incompatible. Both congruences individually have many solutions, but they cannot then be met by the same integer.