PSYCHOCODES

PsychoCodes.in

C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers

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.

If You Love this article, You Should Consider:

  • Like us on Facebook
  • Follow us on Instagram
  • Follow us on Twitter
  • Subscribe to our Newsletter.
  • Let us know your suggestions and queries in the comments below.

Thank you for your Love and Support

Share your thoughts