CoCoA:Mod2Rat

Mod2Rat

reconstructing rationals from modular integers

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

Syntax

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

Div

Mod

   <type>integer</type>
   <type>rational</type>
   <type>zmod</type>