I'm evaluating a psedo-random number generator which generates numbers based on a rule of the form X[n+1] = AX[n] + B(Mod M)
I'm given the first five numbers in the sequence, which are as follows:
x[0]= 56687054115473550533
x[1]= 71501923691929981066
x[2]= 1162551557687152936
x[3]= 88117163952857350660
x[4]= 16754986973331962115
Armed with that information, I'm to figure out what A, B, and M are, so I can calculate subsequent numbers. I'm comfortable solving systems of equations, but am not very familiar with linear algebra/congruences, and am honestly a bit baffled where to even start eliminating variables from the system. I've seen examples of this where A is different across the system, and B and M are constant, but never an example where all 3 are constant.
The crucial point of the problem is determining $M$. We have $4$ equations
\begin{align} 56687054115473550533\,A+B&\equiv 71501923691929981066\,(\mbox{mod }M),\\ 71501923691929981066\,A+B&\equiv 1162551557687152936\,(\mbox{mod }M),\\ 1162551557687152936\,A+B&\equiv 88117163952857350660\,(\mbox{mod }M),\\ 88117163952857350660\,A+B&\equiv 16754986973331962115\,(\mbox{mod }M). \end{align}
First we choose one of the equations, e.g. the $3$rd one, to express $B$ in terms of $A$, i.e., $$B\equiv 88117163952857350660-1162551557687152936\,A\,(\mbox{mod }M).$$ Then we use substitution to cancel $B$ from the other $3$ equations to get \begin{align} 55524502557786397597\,A+16615240260927369594&\equiv 0\,(\mbox{mod }M),\\ 70339372134242828130\,A+86954612395170197724&\equiv 0\,(\mbox{mod }M),\\ 86954612395170197724\,A+71362176979525388545&\equiv 0\,(\mbox{mod }M). \end{align} Then we use the $1$st equation to cancel $A$ from the other equations using elimination by addition and subtraction. We are not allowed to use division. We have \begin{align} 55524502557786397597\times 86954612395170197724-70339372134242828130\times 16615240260927369594\equiv 0\,(\mbox{mod }M),\\ 55524502557786397597\times 71362176979525388545-86954612395170197724\times 16615240260927369594\equiv 0\,(\mbox{mod }M). \end{align} So $M$ is a common divisor of the two big numbers. Use the Euclidean algorithm to find their greatest common divisor $95034255219577607603$, which factorizes into
$$95034255219577607603=29\times 577\times 210323\times 27003471317.$$
Since it is implicitly assumed that $x[0],x[1],\ldots,x[4]$ are all within $[0,M-1]$, the only possible $M$ is the greatest common divisor itself. Once $M$ is found, $A$ and $B$ can be found using any of the previous equations. So we have \begin{align} A=12630192673789351314,\\ B=35234390061212433526,\\ M=95034255219577607603. \end{align} You can verify that these numbers correctly reproduce the sequence $x[0],x[1]\ldots,x[4]$ from $x[0]$.