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

fracmod(3,13)

−

1
4

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

Note that this means:

-1/4%13

3%13 |  |  |  |  |  |  |  |  |  |

fracmod(13,121)

−

4
9

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