Properties of the modulo operation

Question

I have the compute the sum S = (a*x + b*y + c) % N. Yes it looks like a quadratic equation but it is not because the x and y have some properties and have to be calculated using some recurrence relations. Because the sum exceeds even the limits of unsigned long long I want to know how could I compute that sum using the properties of the modulo operation, properties that allow the writing of the sum something like that(I say something because I do not remember exactly how are those properties): (a*x)%N + (b*y)%N + c%N, thus avoiding exceeding the limits of unsigned long long.

Thanks in advance for your concern! :)

Answer 1

a % N = x means that for some integers 0 <= x < N and m: m * N + x = a.

You can simply deduce then that if a % N = x and b % N = y then

(a + b) % N =
= (m * N + x + l * N + y) % N =
= ((m + l) * N + x + y) % N =
= (x + y) % N =
= (a % N + b % N) % N.

We know that 0 < x + y < 2N, that is why you need to keep remainder calculation. This shows that it is okay to split the summation and calculate the remainders separately and then add them, but don't forget to get the remainder for the sum.

For multiplication:

(a * b) % N =
= ((m * N + x) * (l * N + y)) % N =
= ((m * l + x * l + m * y) * N + x * y) % N =
= (x * y) % N =
= ((a % N) * (b % N)) % N.

Thus you can also do the same with products.

These properties can be simply derived in a more general setting using some abstract algebra (the remainders form a factor ring Z/nZ).

Answer 2

How about this:

   int x = (7 + 7 + 7) % 10;

   int y = (7 % 10 + 7 % 10 + 7 % 10) % 10;

Answer 3

You can take the idea even further, if needed:

S = ( (a%N)*(x%N)+(b%N)*(y%N)+c%N )%N

Answer 4

You can apply the modulus to each term of the sum as you've suggested; but even so after summing them you must apply the modulus again to get your final result.