Multiplicative inverse action

First, let's talk about the inverse element ：
Inverse element
Number theory reciprocal , It is also called inverse element

The reciprocal in number theory has a special meaning

Do you think a The reciprocal of is still in number theory 1/a Do you

(・∀・) Hem ~ naive

Let's first introduce the concept of remainder

(a + b) % p = (a%p + b%p) %p （ Yes ）

(a - b) % p = (a%p - b%p) %p （ Yes ）

(a * b) % p = (a%p * b%p) %p （ Yes ）

(a / b) % p = (a%p / b%p) %p （ wrong ）

Why division is wrong

It's hard to prove right , To prove wrong, just give a counterexample

(100/50)%20 = 2 ≠ (100%20) / (50%20) %20 = 0

For some topics , We must find the remainder in the middle process , Otherwise, the number is too large , The computer can't save , So if there's division in this equation , Are we unable to calculate this formula ？

The answer, of course, is NO (>o<)

Then you need the inverse element

We know

If

a*x = 1

that x yes a Reciprocal ,x = 1/a

however a If not 1, that x It's a decimal

In number theory , In most cases, there is a surplus , So now the problem has changed

a*x = 1 (mod p)

that x It must be equal to 1/a Do you

not always

So at this point , We will take x as a Reciprocal , Just add a remainder condition , therefore x be called a About p Inverse element

such as 2 * 3 % 5 = 1, that 3 Namely 2 About 5 Inverse element , Or say 2 and 3 About 5 It's the opposite of each other

In summary

set up c yes b Inverse element , Then there are b*c≡1(mod m);
inference ：(a/b)mod m = (a/b)1mod m = (a/b)bc mod
m=ac(mod m); namely a/b The modulus of is equal to a * (b Inverse element ) The mold ;
This corollary explains why the inverse element is introduced ;

Function of inverse element
A word is , Change division to multiplication ;

for example seek (A / B) %p ; stay B When the value of is very large ,B As divisor , It is very likely that the precision will explode ; The divisor cannot be too large ; So we can turn it into multiplication to solve ;

(a/b)mod m = (a/b)*1mod m = (a/b)bc mod
m=ac(mod m);
namely a/b The modulus of is equal to a * (b Inverse element ) The mold ;
So the steps of finding this formula according to this inference are clear ;

Find out B Inverse element （ Extended Euclid , Fermat lemma + Fast power ） Can find ;
Just quote formula inference and apply it ;