Expressing a fraction as a natural number under modulo ' m ' | Function to return the GCD of given numbers ; Recursive function to return ( x ^ n ) % m ; Function to return the fraction modulo mod ; ( b ^ m - 2 ) % m ; Final answer ; Driver code
< ? php function abc ( $ a , $ b ) { if ( $ a == 0 ) return $ b ; return abc ( $ b % $ a , $ a ) ; } function modexp ( $ x , $ n ) { $ m = 1000000007 ; if ( $ n == 0 ) { return 1 ; } else if ( $ n % 2 == 0 ) { return modexp ( ( $ x * $ x ) % $ m , $ n / 2 ) ; } else { return ( $ x * modexp ( ( $ x * $ x ) % $ m , ( $ n - 1 ) / 2 ) % $ m ) ; } } function getFractionModulo ( $ a , $ b ) { $ m = 1000000007 ; $ c = abc ( $ a , $ b ) ; $ a = $ a / $ c ; $ b = $ b / $ c ; $ d = modexp ( $ b , $ m - 2 ) ; $ ans = ( ( $ a % $ m ) * ( $ d % $ m ) ) % $ m ; return $ ans ; } $ a = 2 ; $ b = 6 ; echo ( getFractionModulo ( $ a , $ b ) ) ; ? >