C167CS mystery

Hello all,
This is the deal: 2 identical controllers of type C167CS. The requirement is that one product cannot be used without the other, so I devised a simple authentication protocol:

R(n) = ( (A * R(n-1) + C) mod M)

is computed on both products, where R(n) is an 32 bit integer, and A = 1366, C = 150889, M = 714025 the seed R(n-1) is selected by assigning the clock value to it. The clock value is added or subtracted from the constants A, C and M depending if it is add or not. One product sends the clock value and the selected offset over a CAN bus and the other reconstructs the answer and sends it back. If the answers match - product is authenticated.
I wrote the code about 2 weeks ago, tested it and checked in. But today, the same code did not function anymore. I managed to get it to work, but only after making the following modifications:
* working with constants that limit the range of the intermediate results to 16 bit width.
* remove the modulus operator.

I also encounter problems with comparing two 32 bit integers. I had to compare these numbers in 2 stages, 16 bits each. I admit that I did not thoroughly check the generated assembly.
Can you offer an explanation? How come it worked over the course of several hours and then - not anymore? (for clarity: the product's answers did not agree anymore).
Are all the assumptions of all moderns computing false :-) ?