Modular multiplicative inverse | 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
< ? php function modInverse ( $ a , $ m ) { $ m0 = $ m ; $ y = 0 ; $ x = 1 ; if ( $ m == 1 ) return 0 ; while ( $ a > 1 ) { $ q = ( int ) ( $ a / $ m ) ; $ t = $ m ; $ m = $ a % $ m ; $ a = $ t ; $ t = $ y ; $ y = $ x - $ q * $ y ; $ x = $ t ; } if ( $ x < 0 ) $ x += $ m0 ; return $ x ; } $ a = 3 ; $ m = 11 ; echo " Modular ▁ multiplicative ▁ inverse ▁ is STRNEWLINE " , modInverse ( $ a , $ m ) ; a . . . >