You should be able to solve this

A common algorithm for generating pseudorandom numbers is a "linear congruential generator" which uses the following procedure:

1) A positive integer m and two integers a and b between 0 and m−1 are fixed.

2) A seed r(0) between 0 and m−1 is input.

3) After that, numbers are generated by the recurrence r(n+1) = ar(n)+b (mod m).  (So that 0 <= r(n+1) <= m−1).


The following sequence of numbers was generated in this way.

6543
6331
9584
9025
3911

Find a,b, and m.

(crossposted from /sci/, cuz i herd u liek math).

>>23
Fair enough, but the ingenuity to come up with something a little more subtle than a brute-force search is frequently helpful as well.


We know:

6543a + b = 6331 (m)
6331a + b = 9584 (m)
9584a + b = 9025 (m)
9025a + b = 3911 (m)

Eliminate b by subtracting successive equations

212a = -3253 (m)
-3253a = 559 (m)
559a = 5114 (m)

Eliminate a from the first two by multiplying the first by -3253, the second by 212, and subtracting.  Same for the next pair:

0 = (-3253)(-3253) - (212)(559) = 10463501 (m)
0 = (559)(559) - (-3253)(5114) = 16948323 (m)

So m has to divide gcd(-10695403, 16948323) = 14159.  Since two of the given numbers are bigger than 14159/2 (or since 14159 is prime), m must be exactly 14159.

Now since gcd(212,14159) = 1, the equation from above:

212a = -3253 (14159)

determines a, and we can solve this to get a = 9001.  Then plug into one of the first 4 to get b = 69.

:P