Mod Inverse - Concept

Hello Everyone , today we will be discussing an important concept of competitive programming .

It is MOD INVERSE .

So when you arrive at a number and you need to mod it , you can us the % operator .

But what happens when the thing you want to mod is a fraction of the form p/q .

Then we have to use mod inverse .

So we mod p as usual and multiply it to modinverse of q and then take the mod of this multiplication to get a number in bound.

So what exactly is mod inverse of q , it is basically a number which when multiplied to q leaves  remainder of one when modded .

This means mod inverse of q with respect to a is a number x which satisfies (q*x)%a=1 .

So , you could naviely try all the numbers to find x , but that is tedious , so we just use a property to ind this number fast .

The property is (p^(a-1))%a=1 , where a is any number .

So, we the modinverse of q with respect to a is (q^(a-2))%a .

As this when multiplied to q will give q^(a-1) which % a is 1

Thank you folks , do follow and subscribe my channel