Multiplicative Inverse

general
1

How to proceed for calculating the multiplicative inverse of number when M is not prime.
Eg. if M= 7 the MMI of 4 is 2 as

( 4 * 2 ) %7 ==1

,
if M=11, the MMI of 7 is 8 as

( 7 * 8 )%11 ==1

,
if M=13, the MMI of 7 is 2 as

( 7 * 2 ) % 13==1

.
When M and the other number are co-prime,only then it can be calculated as above.
Is there a way to do it when they are not co-prime?
How to solve such problems?
Thanks!

1 Like
2

if you are talking about modulo arithmetic, then as i remember (a*b)%c = (a*(b%c))%c.

so maybe you can try and apply recursion to evaluate your desired results.

Let me know if that is what you needed.

3

The modular multiplicative inverse of an integer a modulo m is an integer x such that

a^{-1} equiv x(mod{m}).

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to

ax equiv a*a^{-1} equiv 1 (mod{m}).

The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1).

1 Like
4

The modular multiplicative inverse of an integer x modulo m is (x^(ETF(m)-1))%m where ETF is Euler’s Totient Function. But multiplicative inverse of x mudulo m exists only if x and m are coprime.

2 Likes
5

Thank you @acodebreaker2 and @anikaitshivam for your answers :slight_smile: .So,inference can be drawn that,multiplicative inverse of a modulo b exists if and only if a and b are co-prime.
Euler’s totient function can be used to find modular multiplicative inverse. Is there any other way out,a simple one?
Its somewhat complicated.How to go for following:-

int a,b,m=1000;
int c=(a/b)%m;

In case of division,normal modulo properties are not applied.
**NOTE:**m is not a prime.

6

@aaha97
Yeah,m talking about modulo arithmetic,but for division.For eg:- (a/b)%c.This can be easily evaluated as (a*(MMI of b)%c)%c,when b and c are co-prime.What if they aren’t co-prime?