Intrinsic relations in the structure of linear congruential generators modulo \(2^ \beta\) (Q1202294)

The linear congruential generator defined by \(x_{i+1}=ax_ i+b\bmod 2^ \beta\) is considered. By choosing \(a=1+A2^ \alpha\), \(A\) odd, \(1<\alpha\) integer, \(b\) odd, the above sequence has a period \(2^ \beta\), but the effective period is \(2^{\beta-\alpha}\) as found by \textit{G.Marsaglia} [Appl. Number Theory Numer. Anal. 1971, 249-285 (1972; Zbl 0266.65007)]. In a previous work the authors [J. Comput. Phys. 77, No. 1, 267-269 (1988; Zbl 0644.65003)] derived a general relation \(\sum_{j=0}^ \ell c_ j x_{n+j2^{\beta-\alpha s}}=0\bmod 2^ \beta\). In the present work the relation \(\sum_{j=0}^ s{s \choose j}(-1)^ j x_{n+j+2^{\beta-\alpha s}}\equiv \sum_{j=0}^ s {s \choose j}(- 1)^ j x_{n+j}\bmod 2^ \beta\) is found. These two relations are equivalent only in the case of \(s=1\).