inverse part is not clear
Inverse part is not clear
which part from the video please tell the timestamp
the whole intuition behind crt and specifically at 17:45, how is the inv calculated
Hello @yash_jjw,
Sir has explained the the formula and the meaning of inv at 11:25
inv[i]= modular multiplicative inverse of pp[i] w.r.t. num[i].
so, inv[i] is a number which when multiplied with pp[i] and on taking modulus of the product with num[i] gives 1 as result. i.e.
(pp[i] * inv[i]) % num[i] = 1
Now, let’s understand the entire intuition:
Given formula was:
x = ( ∑ (rem[i]*pp[i]*inv[i]) ) % prod
Where 0 <= i <= n-1
So, sir has explained it’s derivation:
Example:
we have to find x such that it satisfied the following system of linear congurances:
x % 2 = 1
x % 3 = 2
x % 7 = 5
So, x can be written as ’
x= contribution of 2’s remainder + contribution of 3’s remainder + contribution of 7’s remainder …(i)
contribution of 7’s remainder = 237/7 = 2*3 = pp[7]
Now, we know, on dividing with 7, the remainder should be 5, but here it is coming out to be 2*3=6
So, we can take a value say y[7] which on multiplying with pp[7] and on modulus with 7 gives 5 as remainder i.e
(pp[7] * y[7]) % 7(i.e. num[7]) = 5…(1)
As per the formula of inv[7]:
(pp[7]*inv[7]) % 7 = 1…(2)
using (2) in (1),
(pp[i]* inv[7] * 5) % 7 = 5
But 5 is rem[7],
So, actual contribution of remainder of 7 = (pp[2]* inv[7] * rem[7]) % 7
Similarly,
actual contribution of remainder of 7 = (pp[2]* inv[2] * rem[2]) % 2,
and actual contribution of remainder of 7 = (pp[3]* inv[3] * rem[3]) % 3
by replacing above to in (i), you’ll get the required equation.
Refer to the following for detailed explanation:
Hope, this would help.
Give a like if you are satisfied.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.