CODEWITHSUNDEEP
mathnumbersmodulo
Born Again
Born Again

Reputation: 2179

How to simplify modulo

I am trying to find the modulo of an expression. All I know is that

(a+b) mod N = ((a mod N) + (b mod N)) mod N

How do I use it to simplify the following modulo operation?

(a - 2*b + 1) mod N

There must be some way to simplify it by considering it as

(a - b - b + 1) mod N ?

EDIT:

I have stumbled upon the following property too:

ab mod N = ((a mod N) (b mod N)) mod N

Will this be helpful somehow?

Upvotes: 0

Views: 7278

Answers (2)

doog abides
doog abides

Reputation: 2288

If: (a+b) mod N = ((a mod N) + (b mod N)) mod N

then:

(a - 2*b + 1) mod N = ((a mod N) - (b mod N) - (b mod N) + (1 mod N)) mod N

It is simpler with large values of a and b and a small value for N.

For example: a=85773, b = 77733340, N=5: which would you rather solve

(85773 - 77733340 - 77733340 + 1) mod 5

or

((85773 mod 5) - (77733340 mod 5) - (77733340 mod 5) + (1 mod 5)) mod 5

for the second one i get (3 - 0 - 0 + 1) % 5 = 4

Upvotes: 1

dezman
dezman

Reputation: 19358

There is no way to simplify (b*-2 + a + 1) % n unfortunately.

Upvotes: 1

Related Questions