##  [Rational Reconstruction](/rational-reconstruction-0) 

 Definition

A family of algorithms to recover a rational number p/q from its image modulo an integer N or from an approximate modular residue, under size bounds on numerator and denominator, typically using continued fractions or the extended Euclidean algorithm.

 

 

 

 

 

 





## Principle

Principle

Interpret the residue r ≡ p·q^{-1} (mod N) as a rational approximation r/N and compute convergents via continued fractions or use extended gcd to find small integers (p,q) satisfying |p|≤P, 0

 

 

 

 

 





## Demonstration

Demonstration

Concrete example: take N=97 and suppose r ≡ 57 corresponds to p/q with q≤12. Compute that the modular inverse of 12 is 89, 5·89≡57 (mod 97), hence r=57 can be reconstructed as 5/12 by continued‑fraction/extended‑gcd verification under the bound q≤12.

 

 

 

 

## Misapplication

Misapplication

Attempting reconstruction without valid size bounds (denominator too large) or from residues derived after reduction with insufficient modulus N, which can yield incorrect rational candidates or multiple spurious solutions.

 

 

 

 

 





## Consequence

Consequence

Enables recovery of exact rational coefficients from modular computations, modular reconstruction in computer algebra and rational interpolation, and robust reconstruction in algorithms that avoid large‑integer arithmetic until postprocessing.

 

 

 

 

## Reversal

Reversal

The forward mapping (reduce p/q modulo N to obtain residue r) is straightforward; reconstruction inverts this mapping but requires external size constraints — reversing without bounds yields ambiguity instead of unique recovery.

 

 

 

 

 





## Boundary

Boundary

Requires explicit bounds on numerator and denominator and an N chosen large enough to avoid collisions; applies to rational numbers with moderate numerator/denominator sizes and integer moduli; does not apply to irrational numbers or rationals with arbitrarily large denominator relative to N.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension between modular image equivalence classes (many rationals map to the same residue) and uniqueness achieved only under size bounds; tension also between continued‑fraction approximations and direct lattice/Euclidean approaches.

 

 

 

 

 





## Synthesis

Synthesis

Rational reconstruction unites modular arithmetic and Diophantine approximation: given a residue and size bounds, continued fractions or extended gcd produce the unique small rational whose modular image matches the residue, recovering exact rationals from modular or reduced data.