View Single Post
Old 2010-12-07, 22:42   #8
CRGreathouse's Avatar
Aug 2006

172516 Posts

Originally Posted by science_man_88 View Post
I know (a*b) mod x = (a mod x * b mod x)mod x, I've thought about addition and a few others as well looks like it holds for other operations.
Originally Posted by 3.14159 View Post
Operations using modular arithmetic;

(a mod x + b mod x) mod x = (a + b) mod x.

(a mod x * b mod x) mod x = (a * b) mod x.
Yes. But it's sometimes useful to reduce only partially: (a - Ax)(b - Bx) mod x = a * b mod x. This is used in some efficient algorithms where fully reducing at each step would be more costly.
CRGreathouse is offline   Reply With Quote