# numlib::reconstructRational

Rational number reconstruction

### Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

## Syntax

```numlib::reconstructRational(`a`,`n`)
```

## Description

`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.

## Examples

### 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, [x]):```

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)`

`gcd(f,g)`

## Parameters

 `a` An integer `n` A positive integer

## Return Values

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

## References

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