Question

Project 2: The Inverse Modulo n [MOD] Textbook Section: 7.37 Directions: The user will input the modulus п they want to work in ( n > 1 ) along with the integer whose inverse they want to find 0<а). Соmputeе a^f-1}$$by implementing one of the standard algorithms: Euclidean Algorithm, Gauss's Algorithm, Fermat's Little Theorem, Euler's Totient Function, or Chinese

Answer 1

CODE IN C++

#include<iostream>

using namespace std;

int GCD(int a, int b, int *x, int *y)

{

  if (a == 0)

  {

    *x = 0, *y = 1;

    return b;

  }

  int x1, y1;

  int gcd = GCD(b%a, a, &x1, &y1);

  *x = y1 - (b/a) * x1;

  *y = x1;

  return gcd;

}

void modInverse(int a, int m)

{

  int x, y;

  int g = GCD(a, m, &x, &y);

  if (g != 1)

    cout << "Inverse does nOt exist!!";

  else

  {

    int res = (x%m + m) % m;

    cout << "Modular inverse is " << res;

  }

}

// Driver Program

int main()

{

  int a, n;

cout << "Enter the value of n: ";

cin >> n;

cout << "Enter the value of a (>= 0): ";

cin >> a;

  modInverse(a, n);

  return 0;

}