Hi Guys,
suppose a number N when divided by numbers x and y leaves a remainder r1 and r2 respectively
ie., N mod x = r1 and N mod y = r2
What is N mod (x*y)
Please help me understand the logic behind this scenario
Thanks,
Sai
It's been a while, but I'll take a stab at it anyway.
"r1" and "r2" are classes of numbers.
ex. r1 = { ... r1 - 2x, r1 - x, r1, r1 + x, r1 +2x ...}
so,
N mod x = r1 <=> r1 + nx = N, for n integer (1) (def'n)
N mod y = r2 <=> r2 + my = N, for m integer (2) (def'n)
(with n not necessarily equal to m)
x*y = [(N-r1)(N-r2)]/nm, by (1) and (2)
Let p = N mod(x*y) <=> p + l [[N-r1)(N-r2)]/nm] = N (def'n), for l integer.
then p = N - (l/nm)[(N-r1)(N-r2)]