Previous Up Next

5.32.12  Rebuild a fraction from its value modulo p : fracmod

fracmod takes two arguments, an integer n (representing a fraction) and an integer p (the modulus).
If possible, fracmod returns a fraction a/b such that

p
2
 < a ≤ 
p
2
,    0 ≤ b < 
p
2
,     n × b =a (mod p ) 

In other words n=a/b(mod p ).
Input :

fracmod(3,13)

Output :

-1/4

Indeed : 3*−4=−12=1 (mod 13), hence 3=−1/4%13.
Input :

fracmod(13,121)

Output :

-4/9

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


Previous Up Next