In this article, we will learn how to create a program to calculate Inverse Modulo or Modular Multiplicative Inverse of two relatively prime numbers in C programming language but first, let us understand what is Inverse modulo.

The Modular Multiplicative Inverse is an integer 'x' such that

Also Read: Binary Search Program in C using Recursion

`a x = 1 mod n`

or you can represent the above equation as.

`x = (a^-1)modn`

The multiplicative inverse will only exist if a and m are relatively prime (if gcd(a,n)==1). Now let's see the pseudo code to calculate Inverse Modulo of a and n where a and n are relatively prime.

```
solving for imod
where,
imod = (a^-1)modn
1. let i = 0
2. calculate x = n * i + 1
3. if x mod a == 0
imod = x/a(quotient)
goto step 7
5. i = i + 1
6. goto step 2
7. exit
```

We have the steps to calculate Modular Multiplicative Inverse/ Inverse Modulo now let's code a C function for the above pseudo code.

```
int imod(int a,int n){
int c,i=1;
while(1){
c = n * i + 1;
if(c%a==0){
c = c/a;
break;
}
i++;
}
return c;
}
```

In the above code, we have declared two variable** c**(the **imod** variable) and **i** then we are calculating **(n * i + 1)** and storing it in variable **c** in a condition based loop which will break out when it will find a number which will completely divide the value stored in variable c and the quotient of the performed division operation will be our inverse mod of **a** and **n**.

Now we need to check if the numbers entered by the user are relatively prime or not for that we are going to write a GCD function for validation.

```
int gcd(int a, int n){
int gcd, i;
for(i=1; i <= a && i <= n; ++i){
if(a%i==0 && n%i==0)
gcd = i;
}
return gcd;
}
```

Now let's write the driver function and complete our program.

#### Modular Multiplicative Inverse program in C

```
#include<stdio.h>
int gcd(int a, int n){
int gcd, i;
for(i=1; i <= a && i <= n; ++i){
if(a%i==0 && n%i==0)
gcd = i;
}
return gcd;
}
int imod(int a,int n){
int c,i=1;
while(1){
c = n * i + 1;
if(c%a==0){
c = c/a;
break;
}
i++;
}
return c;
}
int main(){
int a,n,mod;
printf("Enter the value of a and n: ");
scanf("%d%d",&a,&n);
if (gcd(a,n)==1)
printf("The Modular Multiplicative Inverse is: %d\n",imod(a,n));
else
printf("The numbers are not relatively prime.\n");
return 0;
}
```

**Output:**

```
Enter the value of a and n: 343 158400
The Modular Multiplicative Inverse is: 12007
```

Thank you for reading the article.

Special Thanks to Ashish Ghadi for providing the steps to calculate Modular Multiplicative Inverse.

## Share your thoughts