The problem
Let $m=p\cdot q$, where $p,q$ are primes. The LCG is $x_i=(ax_{i-1}+b)\mod m$, where $0<a<m$, $0\leq b<m$ and $0\leq x_0<m$.
I need to show that (without Hull-Dobel theorem) if $m$ is such that:
- $\text{GCD}(b,m)=1$,
- if $m$ is divisible by some prime $p$, then $(a-1)$ is divisible by $p$,
- if $m$ is divisible by $4$, then $(a-1)$ is divisible by $4$,
the LCG reaches it's maximum cycle length.
What I have
When $p\neq q$ the proof is pretty straight forward, from the second condition I get that $a=1$, from that $x_i=(x_0+i\cdot b)\mod m$ and then $m|i$. Also I know how to prove it when $p=q=2$.
Where I'm stuck
I don't know how to prove it when $p=q$. How should the proof go? What should I do? What am I missing?
When $p = q \ne 2$, from the second condition we have $a = np + 1$, where $0\le n\le p-1$ is an integer.
We now claim that $x_i \equiv (inp + 1)x_0 + \left(\frac{i(i-1)}{2}np + i\right)b \pmod{p^2}$.
For $i = 0$ it is obviously true.
Assume it is also true for $i = k$.
Then $x_{k+1} = ax_k + b \equiv (np + 1)\left((knp + 1)x_0 + \left(\frac{k(k-1)}{2}np + k\right)b\right) + b \pmod{p^2}$
$\equiv (knp + np + 1)x_0 + \left(\frac{k(k-1)}{2}np + knp + k + 1\right)b \pmod{p^2}$
$= ((k+1)np + 1)x_0 + \left(\frac{(k+1)k}{2} + k + 1\right)b$
Thus, the claim is true by induction.
Assume $\exists$ $i, j$ such that $x_i = x_j \pmod{p^2}$.
Then compute $x_i - x_j$
$= (inp + 1)x_0 + \left(\frac{i(i-1)}{2}np + i\right)b - (jnp + 1)x_0 - \left(\frac{j(j-1)}{2}np + j\right)b$
$= (i-j)npx_0 + \frac{(i-j)(i+j-1)}{2}np + (i-j)b$
Since it is divisible by $p^2$ (and hence $p$), and $\gcd{(b,p)} = 1$, we have $i-j=0\pmod p$.
Then now the first two terms are divisible by $p^2$, so we further have $i-j=0\pmod{p^2}$.
Therefore, the period attains its maximum at $p^2 = m$.