6.34.12  Rebuilding a fraction from its value modulo p: fracmod iratrecon

Given an integer n and a modulus p, the fracmod (or iratrecon, for Maple compatibility) command finds the rational number equal to n modp, 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.

• Input:
  fracmod(3,13)
  Output:

  −

  1 4

  Indeed: 3*−4=−12=1 (mod 13), hence 3=−1/4%13.
  Note that this means:
  Input:
  -1/4 % 13
  Output:

  3%13

• Input:
  fracmod(13,121)
  Output:

  −

  4 9

  Indeed: 13×−9=−117=4 (mod 121) hence 13=−4/9%13.