Rational number reconstruction
MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.
MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.
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