Find GCD between the sum of two given integers raised to the power of N and their difference | Python program for the above approach ; Function to find the value of ( a ^ n ) % d ; Stores the value of ( a ^ n ) % d ; Calculate the value of ( a ^ n ) % d ; If n is odd ; Update res ; Update a ; Update n ; Function to find the GCD of ( p ^ n + q ^ n ) and p - q mod d ; If p and q are equal ; Stores GCD of ( p ^ n + q ^ n ) and ( p - q ) mod d ; Stores the value of ( p - q ) ; Stores square root of num ; Find the divisors of num . ; If i divides num ; Stores power of ( p ^ n ) mod i ; Stores power of ( q ^ n ) mod i ; Stores power of ( p ^ n + q ^ n ) mod i ; If ( p ^ n + q ^ n ) is divisible by i ; Calculate the largest divisor . ; If i divides num , ( num / i ) also divides num . Hence , calculate temp . ; If ( p ^ n + q ^ n ) is divisible by ( num / i ) ; Calculate the largest divisor . ; Driver code ; Given p , q and n ; Function Call
import math NEW_LINE mod = 1000000007 ; NEW_LINE def power ( a , n , d ) : NEW_LINE INDENT res = 1 ; NEW_LINE while ( n != 0 ) : NEW_LINE INDENT if ( ( n % 2 ) != 0 ) : NEW_LINE INDENT res = ( ( res % d ) * ( a % d ) ) % d ; NEW_LINE DEDENT a = ( ( a % d ) * ( a % d ) ) % d ; NEW_LINE n /= 2 ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def gcd ( p , q , n ) : NEW_LINE INDENT if ( p == q ) : NEW_LINE INDENT return ( power ( p , n , mod ) + power ( q , n , mod ) ) % mod ; NEW_LINE DEDENT candidate = 1 ; NEW_LINE num = p - q ; NEW_LINE sq = ( int ) ( math . sqrt ( num ) ) ; NEW_LINE for i in range ( 1 , sq ) : NEW_LINE INDENT if ( num % i == 0 ) : NEW_LINE INDENT X = power ( p , n , i ) ; NEW_LINE Y = power ( q , n , i ) ; NEW_LINE temp = ( X + Y ) % i ; NEW_LINE if ( temp == 0 ) : NEW_LINE INDENT candidate = max ( candidate , i ) ; NEW_LINE DEDENT temp = ( power ( p , n , num / i ) + power ( q , n , num / i ) ) % ( num / i ) ; NEW_LINE if ( temp == 0 ) : NEW_LINE INDENT candidate = max ( candidate , num / i ) ; NEW_LINE DEDENT DEDENT DEDENT return candidate % mod ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT p = 10 ; NEW_LINE q = 6 ; NEW_LINE n = 5 ; NEW_LINE print ( ( int ) ( gcd ( p , q , n ) ) ) ; NEW_LINE DEDENT