TAOCP 3.2.2 Exercise 34
Let M=\begin{pmatrix} 0&1\\ a&c \end{pmatrix},
Exercise 34. [M25] Prove that the inversive congruential sequence (12) has period $p + 1$ if and only if the polynomial $f(x) = x^2 - cx - a$ has the following two properties: (i) $x^{p+1} \bmod f(x)$ is a nonzero constant, when computed with polynomial arithmetic modulo $p$; (ii) $x^{(p+1)/q} \bmod f(x)$ has degree 1 for every prime $q$ that divides $p+1$. [Hint: Consider powers of the matrix $\binom{0\ 1}{a\ c}$.]
Verified: yes
Solve time: 1m12s
Solution
Let
$$ M=\begin{pmatrix} 0&1\ a&c \end{pmatrix}, $$
and consider the inversive congruential sequence (12),
$$ X_{n+1}\equiv aX_n^{-1}+c \pmod p . $$
As in the discussion preceding the exercise, the fractional linear transformation
$$ x\mapsto \frac{a+cx}{x} $$
is represented by the matrix $M$. If
$$ M^n= \begin{pmatrix} \alpha_n&\beta_n\ \gamma_n&\delta_n \end{pmatrix}, $$
then the $n$th iterate of the transformation is
$$ x\mapsto \frac{\alpha_n x+\beta_n} {\gamma_n x+\delta_n}. $$
The sequence has period $p+1$ precisely when this transformation has order $p+1$ in the projective linear group over $\mathbf F_p$.
Let
$$ f(x)=x^2-cx-a. $$
By the Cayley-Hamilton theorem,
$$ M^2-cM-aI=0, $$
hence every polynomial identity satisfied by $x$ modulo $f(x)$ is satisfied by $M$. Therefore the ring generated by $M$ over $\mathbf F_p$ is isomorphic to
$$ \mathbf F_p[x]/(f(x)), $$
under the correspondence $x\leftrightarrow M$.
Assume first that the inversive congruential sequence has period $p+1$. Then the corresponding projective transformation has order $p+1$, so
$$ M^{p+1}=\lambda I $$
for some nonzero $\lambda\in\mathbf F_p$; otherwise the induced projective transformation would not be the identity after $p+1$ steps.
Translating this relation through the isomorphism
$\mathbf F_p[x]/(f(x))\cong\mathbf F_p[M]$ gives
$$ x^{p+1}\equiv \lambda \pmod{f(x)}. $$
Since $\lambda\ne0$, condition (i) follows.
Now let $q$ be any prime divisor of $p+1$. If
$$ x^{(p+1)/q}\pmod{f(x)} $$
were a constant $\mu$, then
$$ M^{(p+1)/q}=\mu I. $$
The induced projective transformation would then have order dividing $(p+1)/q$, contradicting the assumption that its order is exactly $p+1$. Hence $x^{(p+1)/q}\bmod f(x)$ cannot be constant. Because reduction modulo a quadratic polynomial yields a polynomial of degree at most $1$, the degree must therefore be $1$. This proves condition (ii).
Conversely, assume that conditions (i) and (ii) hold.
Condition (i) states that
$$ x^{p+1}\equiv \lambda \pmod{f(x)}, \qquad \lambda\ne0. $$
Replacing $x$ by $M$ gives
$$ M^{p+1}=\lambda I. $$
Therefore the induced projective transformation has order dividing $p+1$.
Let $d$ denote its order. If $d<p+1$, some prime divisor $q$ of $p+1$ would satisfy
$$ d\mid \frac{p+1}{q}. $$
Hence
$$ M^{(p+1)/q} $$
would be a scalar matrix. Translating back to the polynomial representation,
$$ x^{(p+1)/q}\bmod f(x) $$
would be a constant polynomial. Condition (ii) excludes this possibility, because it asserts that the reduced polynomial has degree $1$ for every prime divisor $q$ of $p+1$.
Therefore no proper divisor of $p+1$ can be the order of the projective transformation. Since the order divides $p+1$, it must equal $p+1$.
Thus the inversive congruential sequence has period $p+1$ if and only if:
$$ x^{p+1}\bmod f(x) $$
is a nonzero constant, and
$$ x^{(p+1)/q}\bmod f(x) $$
has degree $1$ for every prime divisor $q$ of $p+1$.
This completes the proof.
∎