I'm having a hard time finding an answer to this. I've found several places that discuss it, but they do a very poor job of helping me (specifically me, maybe I'm dumb) understand what they're doing. For the below example, the solution should work for c=0 as well as any other whole number. I've shown values just to be clear that I'm talking about the same equation in the same state, but going forward and in reverse.
I have an LCG: Xn = X×a + c % m (I do believe this is full cycle)
- For: a=67, c=0, m=101, X=1
- Xn = ((1×67) + 0) % 101
- Xn = 67
If I were instead to know the values as follows...
- For: a=67, c=0, m=101, Xn = 67
- 67 = ((X×67) + 0) % 101
- X = ?
... how would I rearrange to solve for X? I am assuming X could only be at max m.
If $\ a\ $ and $\ m\ $ are relatively prime (which is the case for $\ a=67\ $ and $\ m=101\ $, because both are prime), then there is always an integer $\ b\ $ between $1$ and $100$ inclusive such that $\ ba\equiv1\pmod{m}\ $. If you then multiply the congruence $$ X_n\equiv aX_{n-1}+c\pmod{m} $$ by $\ b\ $, you get \begin{align} bX_n &\equiv baX_{n-1}+bc \pmod{m}\\ &\equiv X_{n-1}+bc \pmod{m}\ , \end{align} or $$ X_{n-1}\equiv bX_n+d\pmod{m}\ , $$ where $\ d\ $ is the remainder of $\ (m-b)c\pmod{m}\ $.
For $\ a=67\ $ and $\ m=101\ $, $\ b\ $ turns out to be $\ 98\ $, so the reverse of your equation is $$ X_{n-1}\equiv98X_n \pmod{m}\ . $$ More generally, the usual way of finding the number $\ b\ $ is to use the extended Euclidean algorithm to obtain $\ b\ $ and $\ e\ $ satisfying the equation $\ ab+me=\gcd(a,m)$ ($=1\ $ if $\ a\ $ and $\ m\ $ are relatively prime).