by Mohd Shibli

Posted on 25 January 2018

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.

```
#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.

Preorder and Postorder Traversal of binary tree in Python

02 September 2018

Binary Tree in Python

02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV

17 August 2018

Explaining Register variables in C with examples

17 August 2018

C program to generate all combinations of N-Bit Binary String

10 July 2018

Data Autosave System using PHP, MySQL and AJAX

06 July 2018

3DAJAXAlgorithmsC programmingC ProgramsC TutorialsC-plusplusCMSComputer ScienceCSSData StructuresDjangoHackingHTMLInformation SecurityInterview QuestionsJavaJava ProgramsJava TutorialsJavascriptJavaScript TutorialsJSONOpenCVPHPProgrammingProgramming BooksPythonPython ProgramsSQLSteganographyTechnologyWeb DesigningWeb Development

## Share your thoughts