Is (a/b)mod m == (a mod (b*m)) / b (found it in some solutions of FLOORI4 problem)
Elaborate how’s this possible (Not via example)
Hello Nidhi ,
I think i can help you in understanding this …
So,Let us consider …
((a/b) mod m) = k where k<m note this we are gonna use this soon (equation 1)
It means a/b is must be of the form z*m + k for some z>=0
so we have a/b = z*m + k
multiplying both sides by b. we have
a = zmb + k*b
agree till this ?
now if we take mod with b*m on both sides …
a mod bm = (zmb + kb) mod bm
as mod is distributive over the addition operation … we can write RHS of above equation as
a mod bm = (zmb) % bm + (kb) % bm
zmb is a multiple of bm so it would be zero upto modulo with bm
we have
a mod bm = (kb) % b*m
for equation 1 we know that k<m
so bk < mb where b !=0
there we can say that
a mod bm = kb
or (a mod b*m)/b = k
This is what we want to have … if you find anything incorrect or missing and do comment…
Totally Understood
nice explanation.tnx bro
Thanx for appreciation