Expressing a fraction as a natural number under modulo ' m ' | Java implementation of the approach ; 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
import java . io . * ; class GFG { static long m = 1000000007 ; static long gcd ( long a , long b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } static long modexp ( long x , long n ) { 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 ) ; } } static long getFractionModulo ( long a , long b ) { long c = gcd ( a , b ) ; a = a / c ; b = b / c ; long d = modexp ( b , m - 2 ) ; long ans = ( ( a % m ) * ( d % m ) ) % m ; return ans ; } public static void main ( String [ ] args ) { long a = 2 , b = 6 ; System . out . println ( getFractionModulo ( a , b ) ) ; } }