Modular Multiplicative Inverse

Find the modular multiplicative inverse of the given number with some mod.

Example:

Input:  n = 3 , m = 26
Output: 9

Approach

Java

public class ModularMultiplicativeInverse {
    // declare variable to hold the variable
    static int x = 0, y = 0, d = 0;
    public static void main(String[] args) {
        int a = 3, m = 26;
        gcd(a, m);
        if (d != 1) {
            System.out.println("No modular inverse!");
        } else {
            x = (x % m + m) % m;
            System.out.println(x);
        }
    }
    // method to return GCD and find the
    // coefficient x any y
    // of the equation a*x+b*y=gcd(a,b)
    private static void gcd(int a, int b) {
        // base case
        if (b == 0) {
            // set x=1
            x = 1;
            // set y=0
            y = 0;
            d = a;
        } else {
            // call GCD again
            gcd(b, a % b);
            // hold x value in tmp
            int tmp = x;
            // assign y into x
            x = y;
            // calculate by again
            y = tmp - a / b * y;
        }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//functoon to return GCD and find the 
//coefficient x any y
//of the equation a*x+b*y=gcd(a,b)
int gcd(int a,int b,int &x,int &y)
{
    //base case
    if(b==0)
     {
         //set x=1 
         x=1;
         //set y=0
         y=0;
         return a;
     }
     
     //intermediate variables
     int x1,y1;
     //now call the gcd function 
     int d=gcd(b,a%b,x1,y1);
     //formaula for x as x= y1
     x=y1;
     //formula for  y as x1-y1*(a/b)
     y=x1-y1*(a/b);
    
    //return the gcd
     return d;
}
int main()
{
    int a=3,m=26;
    int x,y;
    int d=gcd(a,m,x,y);
    if(d != 1) {
       cout << "No modular inverse!";
    }
     else {
    x = (x % m + m) % m;
    cout << x << endl;
    }
    return  0;
}
//Time Complexity: O(log(min(a,b)))