Modular Multiplicative Inverse Using EEA

Problem introduction

Write a program to calculate the multiplicative modulo inverse of A with respect to M. The modular multiplicative inverse is an integer x such that.

A x ≅ 1 (mod M) 

The multiplicative inverse of A modulo M exists if, and only if, A and M are relatively prime, i.e., gcd(A, M) = 1. The value of x should be in {0, 1, 2, … M-1}.

Let us take the following example: A = 3 ...