up previous next
Mod2Rat

reconstructing rationals from modular integers
Syntax 

Mod2Rat(Residue:INT, Modulus:INT, DenomBound:INT):RAT

Description
This function determines a rational number equivalent to the given residue modulo the given modulus; the denominator will not exceed DenomBound, and the absolute value of the numerator will be at most Modulus/(2*DenomBound) -- this guarantees uniqueness of the answer. If no such rational exists, or if DenomBound exceeds Modulus/2 then zero is returned. DenomBound must be positive; if not, zero is returned.

Example 
  Mod2Rat(239094665,314159265,10000);
355/113
-------------------------------
  Residue := 1234567;                         -- To compute inverse of
  Modulus := 2^100;                           -- Residue modulo Modulus,
  Mod2Rat(Residue, Modulus, Div(Modulus-1,2));-- result is the denominator.
1/284507170216309247716413542199
-------------------------------


See Also