Rational number reconstruction
This functionality does not run in MATLAB.
p,q of absolute value smaller than
n. It returns
p,q do not exist.
p,q satisfies the following
p is strictly between
If several pairs
p,q satisfy these conditions,
then their ratios
p/q are the same. In such case,
the smallest of these pairs.
Solve this linear congruence: .
Modulo 98, the same congruence has no small solution. The solution
q=1 is not small enough as
7 is not smaller
sqrt(98/2) but just equal.
Rational number reconstruction is mostly used as the last step of a modular algorithm. For example, find the greatest common divisors of the following polynomials.
f:= poly(x^5 + 22/35*x^3 + 3/8*x^2 + 3/35*x + 9/56, [x]): g:= poly(x^5 + 2/5*x^4 + 22/35*x^3 + 153/280*x^2 + 3/35*x + 9/56, [x]):
Typically, you can use
this task. However, suppose you know that the greatest common divisor
has small coefficients with numerator and denominator both smaller
than 10. Then you can use a modular algorithm with a smaller modulus
do: to be able to reconstruct these from their residue class modulo
it is sufficient that
gcd(poly(f, IntMod(211)), poly(g, IntMod(211)))
Rational number reconstruction shows that the constant coefficient
A positive integer
Sequence consisting of an integer and a positive integer, or
 Davenport, J. H. , Y.Siret, and E.Tournier "Computer Algebra: Systems and Algorithms for Algebraic Computation". Academic Press Inc, 1988, p.142