Question

Write a program( preferably in C++)  using the extended Euclidean algorithm to find the multiplicative inverse of a mod n. Your program should allow user to enter a and n.

Note: For this question please make sure the code compiles and runs, it is not copied and pasted from elsewhere( I will be checking!). Thanks

Answer 1

C++ code to find the multiplicative inverse of a mod n:

#include<iostream> 
using namespace std; 

int extended_Euclidean_GCD(int a, int b, int *x, int *y); 

void multiplicative_Inverse(int a, int n) 
{ 
        int x, y; 
        int g = extended_Euclidean_GCD(a, n, &x, &y);
        
        //if not co-primes then inverse doesn't exist 
        if (g != 1)                     
                cout << "Inverse doesn't exist"; 
        else
        { 
                int mul_inv = (x%n + n) % n;        //Adding n to avoid negative x cases
                cout << "The multiplicative inverse is: " << mul_inv; 
        } 
} 

//Recursive function to implement extended euclidean algorithm
int extended_Euclidean_GCD(int a, int b, int *x, int *y) 
{ 
        if (a == 0) 
        { 
                *x = 0, *y = 1; 
                return b; 
        } 

        int X_1, Y_1; 
        int GCD = extended_Euclidean_GCD(b%a, a, &X_1, &Y_1); 
        *x = Y_1 - (b/a) * X_1; 
        *y = X_1; 
        return GCD; 
} 


//Driver main()
int main() 
{ 
        int A,N;
        cout<<"Enter the value of a: ";
        cin>>A;
        cout<<"Enter the value of n: ";
        cin>>N; 
        multiplicative_Inverse(A, N); 
        return 0; 
} 

OUTPUT: