Modular Multiplicative Inverse

[nilshah98]

Do the checklist before filing the issue:

• [ ] Do you have Node.js and all the relevant dev-dependencies installed?
• [ ] Is this a bug fix?
• [x] Is this an enhancement?
• [x] Is this a feature request?

NOTE: Provide a clear and concise description of the feature that needs to be added! Or if its a bug, then provide the necessary steps to reproduce it along with screenshots.

---

In many competitive coding questions it is required to get modulo multiplicative inverse of your answer with some other number, many a times, it's prime - 10^9+7. So, an added functionality to find modulo multiplicative inverse of two numbers.

Maybe a separate function, for when the numbers are prime, coprime, and have factors.

Links- Modular Multiplicative Inverse GFG

[fave77]

[Function: M.modInverse(a, b)]

Validation:

• check for gcd(a, b) = 1 else return an error indicating that a & b aren't relatively prime!
• check for argument type

Category: Mathematical Utilities

[Indrajit1997]

@pbiswas101 For this we need to implement a power function with modulo M in O(log n) time. So, we have to build it as another function of MathBall. Is it okay to make an issue on Power function? .

[fave77]

@Indrajit1997 Alright, you can raise an issue discussing its implementation as M.pow(a, b, m) with the last parameter being optional! So, that it can also be used as M.pow(a, b)

[nilshah98]

@pbiswas101 For this we need to implement a power function with modulo M in O(log n) time. So, we have to build it as another function of MathBall. Is it okay to make an issue on Power function?

The modular multiplicative inverse can be implemented using Extended Euclid Theorem, which doesn't require any power function with modulo M.

Additionally, here are a few points for implementing modulo multiplicative inverse -

1. First need to check whether the numbers are relatively prime or not, ie. having GCD 1.
2. If GCD is 1, proceed to find the modular multiplicative inverse using Extended Euclid Theorem, which won't require any modulo power function.
3. If GCD is anything other than 1, return 0, as 0 can never be a modulo multiplicative inverse of a number.

Example Output -

M.modInv(10,460) = 0;    /* 10,460 not relatively prime, so return 0 */
M.modInv(3,26) = 9;        /* 3,26 relatively prime, so return modulo multiplicative inverse */

Complexity for Extended Euclid as well as Fermat is both - O(Log m)

Validation -

• Should be a function
• Should return 0 for relatively not prime numbers
• Should work for integers, both positive and negative
• Should return errors for anyother combination, except integers

PS: Add more validations, if any

[devRD]

Can I work on this ?

[fave77]

@devRD You're assigned!