GCD of a number raised to some power and another number | Calculates modular exponentiation , i . e . , ( x ^ y ) % p in O ( log y ) ; x = x % p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Returns GCD of a ^ n and b ; Driver code
function power ( x , y , p ) { while ( y > 0 ) { if ( ( y & 1 ) != 0 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } function gcd ( a , b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } function powerGCD ( a , b , n ) { var e = power ( a , n , b ) ; return gcd ( e , b ) ; } var a = 5 , b = 4 , n = 2 ; document . write ( powerGCD ( a , b , n ) ) ;