Engineering / Mathematics — Integer Algorithms
Rational Reconstruction
Recovering a rational number from its residue modulo n, the uniqueness conditions, and the role of the extended Euclidean algorithm.
Executive summary
Rational reconstruction inverts the map that sends a fraction to its residue modulo n. Given the residue and size bounds on numerator and denominator, the fraction is recoverable and unique.
The mechanism is the extended Euclidean algorithm halted partway: the intermediate remainders and coefficients supply exactly the numerator and denominator sought.
Learning objectives
- State the reconstruction problem and its uniqueness condition.
- Use a truncated extended Euclid run to solve it.
- Apply the method to exact rational linear algebra.
01The problem
Rational reconstruction
Given integers n and a, and bounds r, s with 2rs < n, find integers x, y with
x ≡ a y (mod n), |x| < r, 0 < y ≤ s, gcd(y, n) = 1.
The fraction x/y is then the unique rational of that size congruent to a.
Uniqueness
If a solution exists with 2rs < n, it is unique up to a common factor.
Reason. Two solutions would give x₁y₂ ≡ x₂y₁ (mod n), and both sides are bounded in absolute value by rs < n/2, so the congruence forces equality.
02The algorithm
Run extended Euclid on (n, a) and stop at the first remainder below the bound r. The remainder and the accumulated coefficient at that point are the numerator and denominator.
Rational reconstruction
n, a, bounds r and s with 2rs < nthe rational x/y congruent to a mod n, or failure- Initialise (r₀, t₀) = (n, 0) and (r₁, t₁) = (a, 1).
- While r₁ ≥ r:
- Compute q = r₀ div r₁.
- Set (r₀, r₁) = (r₁, r₀ − q r₁) and (t₀, t₁) = (t₁, t₀ − q t₁).
- Set x = r₁ and y = t₁.
- If y < 0, negate both x and y.
- If y > s or gcd(y, n) ≠ 1, report failure; else return x/y.
O(len(n)²) bit operationsThe correctness rests on the invariant rᵢ ≡ a tᵢ (mod n), which holds throughout the extended Euclid run. Stopping at the right moment produces a pair where both quantities are small enough.
03Application to exact linear algebra
A linear system with integer coefficients has rational solutions. Solving it modulo a large enough modulus and reconstructing recovers the exact rational answer without ever forming a fraction.
Solve modularly
Solve the system modulo a prime power or a product of primes, obtaining each component as a residue.
Bound the answer
Use Cramer's rule and Hadamard's bound to bound the numerators and denominators of the true solution.
Reconstruct componentwise
Apply rational reconstruction to each residue with those bounds.
Verify
Substitute the reconstructed solution back into the original system to confirm exactness.
The verification step is worth keeping. Reconstruction can fail silently if the bounds were underestimated, and substitution is a cheap and complete check.
04Frequently asked questions
How is this related to continued fractions?
Closely. The extended Euclid run computes the continued fraction expansion of a/n, and the intermediate pairs are its convergents. Rational reconstruction is the statement that the best rational approximation of bounded denominator is a convergent.
What if no solution exists within the bounds?
Then the residue does not come from a rational of that size, and the algorithm correctly reports failure. In a modular pipeline this signals that more primes are needed to raise the modulus.
Can this recover a rational from a decimal expansion?
The same machinery applies. Given enough digits, continued fraction expansion recovers a rational with small denominator exactly, which is the classical use of the technique.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 66-70.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.