Modular multiplicative inverse | Iterative C ++ 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 y and x ; Make x positive ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ; } int main ( ) { int a = 3 , m = 11 ; cout << " Modular ▁ multiplicative ▁ inverse ▁ is ▁ " << modInverse ( a , m ) ; return 0 ; }