11.8.12  Rebuilding a fraction from its value modulo p

Given an integer n and a modulus p, the fracmod (or iratrecon, for Maple compatibility) command finds the rational number equal to n (mod p ), where both the numerator and denominator are not greater than √p/2 in absolute value.

• fracmod (or iratrecon) takes two arguments:
  • n, an integer (representing a fraction).
  • p, an integer (the modulus).
• fracmod(n,p) (or iratrecon(n,p)) returns, if possible, a fraction a/b such that

  a ≡ n · b (mod p )                   − √ p 2 < a ≤  √ p 2                   0 ≤ b <  √ p 2

  In other words, n≡ a/b(mod p ).

Examples

Indeed, 3·(−4)=−12≡ 1(mod 13 ), hence 3=−1/4%13.

Note that this means:

Indeed, 13·(−9)=−117≡ 4(mod 121 ) and therefore 13=−4/9%13.