CODEWITHSUNDEEP
algorithmmodular-arithmetic
typedef
typedef

Reputation: 33

Modular Inverse of a number

Recently I have read extended euclid's algorithm which is used to find out the modular inverse of a number N whith respect to MOD such that gcd(N,MOD)=1.

But I have a doubt about how to find modular inverse of a number if gcd(N,MOD)!=1?

Upvotes: 0

Views: 201

Answers (1)

Henry
Henry

Reputation: 43728

If gcd(N,MOD)!=1 a modular inverse of N does not exist.

However, in some cases you can still divide by N, i.e. find an X such that A = N * X (mod MOD). This is possible when gcd(N,MOD) divides gcd(A,MOD). To find such an X just divide A, N, and MOD by gcd(N,MOD) and then proceed as normally (gcd(N', MOD') is then 1).

Upvotes: 2

Related Questions