Modular multiplicative inverse | Iterative Java program to find modular inverse using extended Euclid algorithm ; Returns modulo inverse of a with respect to m using extended Euclid Algorithm Assumption : a and m are coprimes , i . e . , gcd ( a , m ) = 1 ; q is quotient ; m is remainder now , process same as Euclid 's algo ; Update x and y ; Make x positive ; Driver code ; Function call
class GFG { static int modInverse ( int a , int m ) { int m0 = m ; int y = 0 , x = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { int q = a / m ; int t = m ; m = a % m ; a = t ; t = y ; y = x - q * y ; x = t ; } if ( x < 0 ) x += m0 ; return x ; } public static void main ( String args [ ] ) { int a = 3 , m = 11 ; System . out . println ( " Modular ▁ multiplicative ▁ " + " inverse ▁ is ▁ " + modInverse ( a , m ) ) ; } }