Modular operation

general
,
1

Is (ab)%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…!

2

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
3

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…??

4

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

5

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

6

okay… thanks @ achaitanyasai… :slight_smile:

7

okay… thanks @anh1l1ator

8

@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
9

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

10

:frowning: i too want to know how will it affect the output
any general case explanation would also be helpful