Is (a*b)%M= ((a%M)*(b%M))%M in any case ,or in some case, or in no case…??

Also suggest me some editorial for the properties of modular operation plzz…!

Is (a*b)%M= ((a%M)*(b%M))%M in any case ,or in some case, or in no case…??

Also suggest me some editorial for the properties of modular operation plzz…!

Hello,

(a . b)%M= ((a%M) . (b%M))%M is true always,Here . indicates : either +,-,* But division does not holds this rule.In case of division, the method is different and is illustrated below :

Let us say you want to calculate (a/b)%M, :

Method-1 : Represent a/b as product of prime factors and apply (x * y)%M=((x%M) * (y%M))%M.

Method-2 :

Let m=b * M;

Now (a/b)%M = (a%m)/b;

For proof of method 2 look HERE

Method-1 is less optimal(take more time to calculate) than method-2 but it works(correct) in all the cases.In case of Method-2 you need to take care of overflows as you are calculating b*M.

If you have any doubts comment below

Best,

Chaitanya.

2 Likes

okay , how will i proceed for method 2 , when b*M create overflows…??

and i hope there are no restrictions in your methods like M should be prime or relatively prime to b…??

If method-2 fails, use method-1. And yes, method-2 has no restrictions like M is prime or relative prime to b,…

Just substitue a=(k1)*M+k2 ,b=(k3) M+k4 then wheen you multiply you get terms M(k1k4+k3k2+M*k3k1)+k2k4 When you take mod over this summation you get this result… It works always

okay… thanks @ achaitanyasai…

@va1ts7_100 : U can refer the below link for proper understanding of modular arthmetic and its properties. https://theoryofprogramming.wordpress.com/2014/12/24/number-theory-modular-arithmetic/

1 Like

what is m-prime constrain in this problem? can someone explain it with example?

i too want to know how will it affect the output

any general case explanation would also be helpful