An integer algorithm can manipulate enormous values without visiting every smaller integer. This is possible because a remainder preserves the divisibility information we need, and a binary digit can describe a large block of repeated multiplication. The essential skill is to identify what survives each compression. We will use a common-divisor invariant for Euclid's algorithm and a product invariant for modular exponentiation, then ask how much work their compact descriptions actually require.
Motivation
Suppose a program must solve . Testing all forty-three residue classes works here, but it explains neither why an answer exists nor how to handle a modulus with hundreds of digits. A greatest-common-divisor computation does both jobs. Its remainders reveal whether an inverse exists, while its substitutions produce the inverse as a certificate that can be checked by one multiplication and one remainder.
Similarly, computing by multiplying exactly times ignores the way was supplied. An exponent with binary digits may be almost . A loop of length is then exponential in the length of that part of the input. Repeated squaring processes its digits, allowing the same mathematical power to be obtained with only linearly many modular multiplications in .
These are exact integer algorithms. Their certificates express equalities and divisibility, without a numerical tolerance. This makes them a useful contrast with the next chapter's approximation guarantees. Exactness does not mean arithmetic is free: multiplying two long integers involves many bit operations, even if we write it as a single product.
Definitions
For integers , the notation means for some integer . For nonnegative integers that are not both zero, their greatest common divisor is the largest positive integer dividing both. We use for . For arbitrary signs, take absolute values before applying the nonnegative algorithm.
For integers and , division with remainder gives unique integers with and . Euclid's algorithm starts with a nonnegative pair and repeatedly replaces it by while . Its output is the first coordinate when the second becomes zero.
Fix a modulus . The congruence means . A residue class can be represented canonically by one of . A modular inverse of is an integer satisfying . It is the class of that is unique when an inverse exists; the integers are different representatives of the same inverse class.
We consider modular exponentiation with an integer base , a nonnegative integer exponent and . The exponent-zero convention is , including the base zero for this algebraic computation. Negative exponents require an inverse and are outside this input specification. Input length means the number of binary digits in the encoded integers, together with fixed delimiters and signs where needed.
Theorem/proposition
Theorem 5.1.1
(Euclid computes a gcd and a Bézout certificate)
For nonnegative integers , not both zero, Euclid's algorithm terminates and returns . There exist integers with . Such coefficients can be computed by recording and substituting the divisions, or by updating coefficient pairs alongside each remainder.
Theorem 5.1.2
(Exactly when modular division is possible)
An integer has an inverse modulo if and only if . More generally, the congruence is solvable if and only if divides . In the solvable case it has exactly distinct solution classes modulo .
Theorem 5.1.3
(Repeated squaring is exact)
Initialize , and . While , multiply by modulo if is odd, replace by , and replace by . On termination, is the canonical representative of . The procedure uses modular multiplications when has binary digits; exponent zero needs none.
The order of instructions in the last theorem matters. The odd-case update uses the old , before squaring it. One may avoid the final unused squaring as an optimization, but the proof below concerns the stated procedure. Writing an invariant against an exact sequence of assignments prevents an ambiguous algorithm from acquiring an apparently rigorous proof.
Proof sketch or proof idea
Proof
(Euclid: invariant, termination and the Bézout certificate)
If , an integer divides both exactly when it divides both . One implication uses ; the other uses . Therefore a Euclidean update preserves the entire set of common divisors, and hence its largest positive member. The second coordinate strictly decreases while positive, so well-ordering gives termination. At a final pair , the gcd is , proving correctness.
Every initial coordinate is an integer combination of the original inputs: and . Whenever two remainders are such combinations, their difference after multiplying one by a quotient is also such a combination. Thus the final nonzero remainder has the form . This is a constructive proof of the certificate, rather than an assertion that suitable coefficients somehow exist. To implement it, store one coefficient pair for each of the two current coordinates and apply the same subtraction to those pairs.
Concept lensStructural
The gcd as the generator of all integer combinations
For not both zero, the set is closed under addition and negation, so it consists of all multiples of its least positive element. That element divides and , and it is a combination of them, so every common divisor divides it: it is . In this description, is invertible modulo exactly when is a combination of and .
Proof
(Inverses and linear congruences)
If , reduction modulo gives . Bézout supplies such when the gcd is one. Conversely an inverse gives for some integer , so every common divisor of divides one. This proves the inverse criterion in both directions.
For the general congruence, any solution gives , so must divide . When it does, divide the integer equation by to obtain
The two new coefficients and are coprime, so there is one solution class modulo . If , this just means every integer satisfies the divided congruence; no inverse theorem with modulus one is needed. In either case the integers representing that class split into exactly classes modulo , represented by for . Distinct listed representatives differ by less than one full modulus and cannot be congruent. Every solution is congruent to one of them.
Proof
(The repeated-squaring invariant)
For repeated squaring maintain
It holds initially. Write the old exponent as , where is zero or one. The updated state has , and , so . Thus the invariant is preserved. The nonnegative exponent decreases until zero. At that point its power contributes one, leaving ; reduction after each multiplication keeps canonical.
Proof X-ray
Preserve information, reduce the parameter
Euclid preserves the set of common divisors while decreasing a remainder. Repeated squaring preserves a product while shortening an exponent. In each proof, preservation establishes partial correctness and the decreasing parameter establishes termination. A decreasing parameter alone would also certify a program that quickly returns the wrong answer.
Worked examples
Worked example 5.1.4
(A gcd calculation that also answers an impossibility question)
Compute , , and , followed by . The gcd is eighteen. Substituting backwards gives . The identity checks the result without repeating the search. It also proves that is impossible: eighteen divides every left side and the modulus, but cannot divide one.
Worked example 5.1.5
(One inverse and several solutions)
For and , the divisions are , , . Hence . The coefficient minus five gives inverse class modulo , and . For a different congruence, reduces by the gcd two to . Since the inverse of three modulo seven is five, . The two answers modulo fourteen are six and thirteen. Checking gives remainders eight from both and .
Worked example 5.1.6
(Four exponent bits replace thirteen factors)
To compute , use . Successive squared residues are , , and , representing powers one, two, four and eight. Multiplying the selected residues gives . Following the stated loop, the states are initially , then , , and . The invariant explains why skipped even-exponent multiplications lose nothing. The final value six for is unused, so an implementation may omit that last square.
To analyze Euclid, first arrange and let both inputs have at most bits. Every two remainder steps reduce a positive remainder by at least a factor of two. Indeed, for consecutive positive remainders , if the reduction already occurred; otherwise because the quotient is one. Thus there are divisions. A conservative bound using ordinary long division at bit operations each is . This is a valid polynomial upper bound, without claiming the sharpest possible implementation bound.
For modular powers, suppose the base has already been reduced modulo an -bit modulus. Residues have at most bits and a product at most bits. Schoolbook multiplication followed by long division costs bit operations per modular multiplication. A -bit exponent therefore gives bit operations for the main loop, when its bits are consumed by advancing an index rather than repeatedly copying the whole remaining quotient. Reading and initially reducing a much longer base has an additional cost depending on that base's length. The storage for a constant number of residues is bits, with another bits if the exponent is retained explicitly.
Common mistakes
Counterexample mode
Canceling a factor that is not invertible
A tempting rule says that implies . Take , , , . Then and , so the hypothesis holds, but is not divisible by six. The rule is valid when , because multiplication by the inverse of preserves equivalence. In general, if , write and divide by : the coprime numbers and force , so cancellation only gives . Here .
Common mistake
(A negative Bézout coefficient is still an inverse)
The inverse coefficient produced by extended Euclid may be negative; in the example and it is . Reducing it to (here ) changes its representative, not its class. Programming languages differ in their signed-remainder conventions, so the mathematical canonical remainder should be implemented explicitly when the input can be negative.
Common mistake
(Judging the cost by the value of the exponent)
A loop of iterations is not polynomial in merely because the loop variable is called an exponent. Conversely, counting multiplications does not establish that computing the full integer takes polynomial space in the input length: that output may have exponentially many digits. Modular reduction is what keeps the intermediate values bounded here.
Summary
Remainders retain common divisors and make Euclid terminate; tracking their linear combinations produces a checkable Bézout identity. That identity characterizes modular inverses and solves all linear congruences. Repeated squaring retains a product invariant while consuming exponent bits. Correctness and efficiency both become clearer once the preserved information, input encoding and arithmetic model are stated explicitly.
Exercises
Exercise 5.1.7
(Compute and find integers satisfying .)
Core
Solution(3)
- 1
Run the divisions
, , , , . The last nonzero remainder is .
- 2
Substitute backwards
.
- 3
State the certificate
The gcd is three and one pair is ; indeed .
Quick check
(Solve , listing every class modulo fifteen. Explain why has no solution.)
Solution · Answer
The gcd is three, so divide to get . The inverse of three is two, hence . Its three classes modulo fifteen are four, nine and fourteen. The second proposed congruence is impossible because three does not divide four.
Quick check
(Compute by squared residues, and state the invariant at exponent zero.)
Solution · Answer
The residues for powers one, two, four and eight are . Since , the answer is . At , the invariant reads , so the returned canonical residue is seven.
Quick check
(A proposed implementation squares before applying the odd-case multiplication. Show its failure on exponent one and explain the repair.)
Solution · Answer
Starting at , squaring first makes the odd-case update use instead of . For , the wrong answer is four rather than two. Use the old base for the odd update, or derive a different invariant for a deliberately different algorithm.
Quick check
(Compare repeated multiplication and repeated squaring when the exponent is . Distinguish the value of the exponent from its binary encoding length.)
Solution · Answer
Repeated multiplication uses on the order of multiplications. Repeated squaring uses on the order of ; the encoding of has bits. With modular reduction each multiplication also has a polynomial cost in the modulus length. Without that reduction, growing output size must be counted separately.