Motivation
An algorithm needs more than examples that happen to work. Its proof must explain what remains true after each update, why the updates eventually stop, and why the final state answers the original question. Integer algorithms make those obligations concrete. The Euclidean algorithm preserves common divisors and linear-combination certificates; binary exponentiation preserves the value of a partly completed power.
Definitions
Definition 4.1.1
(Invariants and a cost model)
A loop invariant is a proposition about the program state that holds before the first iteration and is preserved by every iteration. A termination measure is a nonnegative integer that strictly decreases whenever another iteration is performed. Partial correctness means a terminating computation returns a correct answer; total correctness includes termination. An arithmetic-operation count treats each specified arithmetic operation as one step. Bit complexity counts operations on individual binary digits, so arithmetic on growing integers is not automatically constant cost.
The invariant and the termination measure have different jobs. An invariant alone may hold through an infinite computation. A decreasing measure alone proves that a computation stops, but does not say what its answer means. State both, and then use the stopping condition to extract the desired result.
Theorem/Proposition
Theorem 4.1.2
(Extended Euclid returns a certificate)
For integers , initialize and coefficient pairs , . While , let and simultaneously replace each pair by
On termination, . There are divisions.
Theorem 4.1.3
(Binary exponentiation)
Given , and an integer , initialize . In each iteration while , write with and simultaneously set
The output is . For , it uses at most modular multiplications, counting a square as one multiplication.
Proof sketch or proof idea
Proof
(Extended Euclid: certificate, gcd and termination)
In extended Euclid the certificate invariant is for . It holds initially, and subtracting times one identity from the other preserves it exactly under the simultaneous update. A number divides both remainders before an update exactly when it divides both afterwards. Thus their gcd remains . The new second remainder lies between and the old , proving termination. At the end the first remainder is positive and the second is zero, so the invariant gives the announced certificate.
For the division count, every two successive divisions reduce the relevant positive remainder by at least a factor of two. If the next remainder is already at most half the current one this is immediate; otherwise their quotient is one and the following remainder is their difference, smaller than half. After divisions no positive remainder remains. This is a division count; it does not declare large-integer division constant-time.
Proof X-ray
Three facts with three separate jobs
The Euclid proof combines three facts, and each does one job. The certificate identity survives because the remainder column and both coefficient columns undergo the same linear update ; linearity is the entire reason. The gcd survives because the pairs and have the same common divisors: a divisor of the first pair divides , and a divisor of the second divides . Neither of these uses the choice of ; any integer would do. Termination is the only place where matters, since it gives . The exit condition closes the argument: when , the current is the previous positive , and , so the preserved gcd is the current first remainder and the preserved identity expresses it in terms of and .
Proof
(Binary exponentiation: the unfinished-power invariant)
In binary exponentiation the invariant is . For , the updated state satisfies
Reduction modulo preserves this identity as a congruence. The nonnegative measure strictly decreases until zero. Then the invariant becomes . If , no iteration occurs and the correct result is . Otherwise there is one iteration per binary digit of , each with one square and at most one extra multiplication.
Worked examples
Worked example 4.1.4
(Extended Euclid as verifiable output)
For , the quotients are and the remainders are . Back substitution gives . The output can be checked independently: divides both inputs and is their integer combination. Any common divisor must divide that combination, proving it is the gcd.
Worked example 4.1.5
(A modular inverse from the certificate)
For and , the identity gives . Indeed . If the gcd were greater than one, the same algorithm would instead certify that an inverse is impossible.
Worked example 4.1.6
(Reading an exponent in binary)
Compute with . The states are , , , , . Thus the answer is . Each update uses the old for both the accumulator and square. Using an already squared in the accumulator would represent a different exponent.
Designing an invariant from the desired answer
An invariant is most useful when it connects the current state to the original input. A claim about the current remainders alone might describe their positivity or decreasing order, but it would not explain which input gcd they represent. The gcd-preservation invariant supplies that connection. The coefficient invariant strengthens it further by retaining an explicit expression in the original inputs, even though the current remainders may be much smaller.
The final output needs both kinds of information. A positive integer combination is not automatically the gcd; many combinations are possible. A common divisor is not automatically greatest. Euclid's preservation of all common divisors and the final zero remainder identify the correct value, while the coefficient identity provides a compact certificate. The proof works because the updates maintain precisely the information needed at the stopping state.
For binary exponentiation, it is tempting to say the accumulator always equals the desired answer “so far.” That phrase is too vague to prove anything. The product of the accumulator with the remaining power gives an exact equation tying the state to the original exponent. Once the remaining exponent is zero, the unfinished factor becomes one and the statement becomes the required conclusion. The form of the invariant was chosen to make that final substitution decisive.
Both proofs follow one four-part pattern. Evaluate the invariant in the initial state. Prove that one iteration preserves it, using old values on the right side of every update. Combine the invariant with the exit condition to identify the output. Finally, supply a strictly decreasing nonnegative measure. The first three parts establish partial correctness; the fourth upgrades it to total correctness.
Simultaneous updates and implementation order
Mathematical assignment notation often hides the need to preserve old values. In the Euclidean update, the new first remainder is the old second remainder, while the new second remainder uses both old remainders. If one overwrites the first remainder before computing the second, the expression no longer means what the proof assumes. The same issue applies separately to the two coefficient columns.
A direct implementation can compute all new values into temporary variables, then replace the old state. Another implementation may use a tuple assignment provided its language evaluates the right side before overwriting the left. Either is correct when it matches the mathematical simultaneous update. The important contract is semantic rather than stylistic: the next state must be the one whose invariant preservation was proved.
Signs and zero inputs also belong in the input contract. The theorem is stated for ordered positive inputs so that each division and decreasing-remainder argument is immediate. For general signed inputs, take absolute values, handle a zero input separately, and interchange the inputs if necessary. After obtaining coefficients for the absolute values, adjust their signs and positions to express the gcd in terms of the original inputs. Both-zero inputs require an explicit convention outside the positive-input theorem.
Why binary digits give the right decomposition
Writing the current exponent as twice a quotient plus a bit separates its least significant binary digit. If the bit is one, one copy of the current base is moved into the accumulator. The remaining exponent is even, so its contribution is represented by squaring the base and halving the exponent. If the bit is zero, no copy is moved, but squaring and halving still preserve the total power. Each iteration therefore consumes exactly one binary digit.
This derivation explains the algorithm more clearly than memorizing a sequence of parity tests and squares. It also handles the zero exponent without a special mathematical identity invented after the fact. The loop does nothing, the unfinished exponent is already zero, and the accumulator one is the correct empty product. The computational convention agrees with the algebraic definition of a zeroth power.
At every stage the accumulator and base may be reduced to the standard residue range. This bounds the size of those stored values by the modulus, even though the unreduced power may be enormous. The exponent is not reduced modulo the value modulus; it is halved according to its binary representation. This is why the algorithm works for nonunit bases too, including a base that shares a factor with the modulus. Euler-style exponent reduction and binary exponentiation are distinct methods with different hypotheses.
Concept lensStructural
Exponentiation by squaring needs associativity
The power invariant reorganizes repeated multiplication without changing its order. The same idea works for matrices or any associative multiplication with an identity, provided powers and the accumulator are interpreted in that setting. The modular version additionally reduces representatives after products. No multiplicative inverse is needed, so the method is broader than the theorems about unit orders.
Operation counts depend on the input encoding
An integer's numerical value and the length of its encoding are different measures. A number with a few hundred binary digits can have an enormous value. An algorithm performing one iteration for every integer up to that value may therefore be infeasible even though the input string is short. The binary-exponentiation loop is efficient in the exponent's encoding length because each iteration removes one digit.
The modulus affects the cost of each iteration. Residues with more digits require more work to multiply and reduce. The arithmetic-operation count isolates the control structure, while the bit bound combines it with a particular multiplication and reduction method. Faster integer arithmetic can improve the per-operation cost without changing the proof of the loop invariant. Conversely, using an inefficient representation may worsen implementation performance without altering mathematical correctness.
Euclid's logarithmic number of divisions should be read with the same discipline. The divisions involve integers of changing sizes, and an exact bit analysis must account for those sizes and the chosen arithmetic routines. The result proved here guarantees a short sequence of divisions, not a constant cost for each division. The distinction is especially important when comparing algorithms whose inputs are large integers rather than small machine-sized values.
Verification after computation
A modular-power result can be checked against an independently derived small cycle when such a cycle is known, or against a second decomposition of the exponent in a worked example. The general correctness proof, however, comes from the invariant and applies beyond those convenient examples. Likewise a reported inverse should be checked by multiplying it by the original residue and reducing modulo the modulus. This final check verifies the answer's defining property directly.
For a reported gcd certificate, check the divisibility of both original inputs and the exact linear-combination identity. These checks are particularly effective at detecting sign and update-order errors. They are small because the proof has already shown why they imply the desired conclusion. Good verification is guided by the mathematical specification, not by mechanically repeating every line of the implementation.
Common mistakes
Common mistake
(Overwriting a value before it is used)
Assignments in these formulas are simultaneous. In ordinary code, use temporary variables or carefully ordered assignments; overwriting a coefficient before its old value is used destroys the certificate invariant.
Common mistake
(Linear in the exponent is exponential in its length)
Efficiency also depends on the representation of inputs. An exponent has about bits, so multiplying by itself times can require exponentially many operations in the exponent's input length. Binary exponentiation uses linearly many modular multiplications in that length. If has bits, school multiplication and elementary reduction of two -bit residues take bit operations, giving bit cost for this implementation when . This bound specifies an arithmetic method; it is not a claim that every software library uses that method.
Counterexample mode
Exponent reduction needs a unit base
Claim: for every and every , . Take , , . Then and , so the claim predicts ; but . The dropped hypothesis is from Euler's theorem, and here . With that hypothesis , and writing makes the reduction valid. Binary exponentiation needs no such hypothesis: on its states are , , , and it correctly returns .
Summary
Euclid preserves divisor information and a linear-combination certificate. Binary exponentiation preserves a product containing the unfinished exponent. A decreasing integer measure proves termination in each case, while a declared cost model makes the complexity statement meaningful.
Exercises
Quick check
(Find the inverse of modulo using an integer certificate.)
The final congruence must be checked.
Solution · Answer
, , , . Back substitution yields . Thus the inverse is ; verifies it.
Quick check
(Compute by successive squaring, and state why reducing the exponent modulo would not be a general rule.)
The exponent cycle and the value modulus are different objects.
Solution · Answer
Modulo , , , . Since , . Exponent reduction must use a return exponent such as , not the modulus . Indeed exponents and are congruent modulo , but and .
Quick check
(Run extended Euclid on , . Give the gcd and a certificate, and decide whether is invertible modulo .)
Count the divisions as well; the last nonzero remainder is the answer.
Solution · Answer
, , , , , so after five divisions. Back substitution gives , and indeed . Since the gcd is , not , the number has no inverse modulo : every combination is even, so none equals .