This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.


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.




numlib::reconstructRational(a,n) returns two integers p,q of absolute value smaller than sqrt(n/2) with p congruent to a*q modulo n. It returns FAIL if such p,q do not exist.

numlib::reconstructRational(a,n) returns p,q by solving .

The solution p,q satisfies the following conditions: p is strictly between -sqrt(n/2) and sqrt(n/2), q is strictly between 0 and sqrt(n/2).

If several pairs p,q satisfy these conditions, then their ratios p/q are the same. In such case, numlib::reconstructRational returns the smallest of these pairs.


Example 1

Solve this linear congruence: .

numlib::reconstructRational(7, 12)

Modulo 98, the same congruence has no small solution. The solution p=7, q=1 is not small enough as 7 is not smaller than sqrt(98/2) but just equal.

numlib::reconstructRational(7, 98)

Example 2

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,

Typically, you can use gcd for 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 than gcd would do: to be able to reconstruct these from their residue class modulo n, it is sufficient that , e.g., n=211.

gcd(poly(f, IntMod(211)), poly(g, IntMod(211)))

Rational number reconstruction shows that the constant coefficient must be 3/7:

numlib::reconstructRational(-90, 211)




An integer


A positive integer

Return Values

Sequence consisting of an integer and a positive integer, or FAIL


[1] Davenport, J. H. , Y.Siret, and E.Tournier “Computer Algebra: Systems and Algorithms for Algebraic Computation”. Academic Press Inc, 1988, p.142

See Also

MuPAD Functions

Was this topic helpful?