TAOCP 3.2.2 Exercise 35

Exercise 35. [HM35] How many pairs $(a, c)$ satisfy the conditions of exercise 34?

Verified: yes
Solve time: 2m48s

Exercise 3.2.2.35 [HM35]

Problem: Determine the number of pairs $(a,c)\in \mathbb{F}_p \times \mathbb{F}_p$ satisfying the conditions of Exercise 34, i.e., such that the inversive congruential sequence

$$ x_{n+1} \equiv a x_n^{-1} + c \pmod p, \quad x_n \neq 0 $$

has maximal period $p+1$.

Corrected Solution

Step 1: Translate Exercise 34 conditions into algebra

Let

$$ f(x) = x^2 - c x - a \in \mathbb{F}_p[x]. $$

Exercise 34 shows that the sequence has period $p+1$ if and only if, for a root $\alpha \in \mathbb{F}_{p^2}$ of $f(x)$:

$x^{p+1} \bmod f(x)$ is a nonzero constant, and
For every prime divisor $q$ of $p+1$, $x^{(p+1)/q} \bmod f(x)$ has degree 1.

Let $\alpha$ be a root of $f(x)$ in $\mathbb{F}_{p^2} = \mathbb{F}p[x]/(f(x))$. Then $x \bmod f(x)$ corresponds to $\alpha$ in $\mathbb{F}{p^2}$.

The first condition implies $\alpha^{p+1} \in \mathbb{F}_p^\times$. Since we are in a prime field, scaling by an element of $\mathbb{F}_p^\times$ does not affect the period, so we may normalize $\alpha$ so that

$$ \alpha^{p+1} = 1. $$

The second condition ensures that $\alpha^{(p+1)/q} \notin \mathbb{F}p$ for any prime $q\mid (p+1)$. Equivalently, $\alpha$ has exact order $p+1$ in $\mathbb{F}{p^2}^\times$.

Thus, admissible pairs $(a,c)$ correspond to irreducible quadratics whose roots are primitive $(p+1)$st roots of unity in $\mathbb{F}_{p^2}^\times$.

Step 2: Count primitive $(p+1)$st roots in $\mathbb{F}_{p^2}$

The multiplicative group $\mathbb{F}_{p^2}^\times$ is cyclic of order $p^2 - 1 = (p-1)(p+1)$. The subgroup of elements $\alpha$ satisfying $\alpha^{p+1} = 1$ has order $p+1$.

The number of elements of exact order $p+1$ in this subgroup is

$$ \varphi(p+1), $$

where $\varphi$ is Euler's totient function.

Step 3: Identify the correspondence $(\alpha,\alpha^p) \mapsto (a,c)$

If $\alpha$ is a root of $f(x) = x^2 - c x - a$, the other root is $\alpha^p$, the Frobenius conjugate. Then

$$ f(x) = (x-\alpha)(x-\alpha^p) = x^2 - (\alpha+\alpha^p)x + \alpha\alpha^p. $$

Comparing with $f(x) = x^2 - c x - a$, we obtain

$$ c = \alpha + \alpha^p, \quad a = -\alpha \alpha^p. $$

Since $\alpha$ has order $p+1>2$, we have $\alpha \neq \alpha^p$, so $f(x)$ is irreducible over $\mathbb{F}_p$.

Observe that the map from admissible roots $\alpha$ to pairs $(a,c)$ is 2-to-1: both $\alpha$ and its conjugate $\alpha^p$ produce the same polynomial $f(x)$ and therefore the same pair $(a,c)$.

Step 4: Count distinct admissible pairs $(a,c)$

There are $\varphi(p+1)$ primitive $(p+1)$st roots $\alpha$ in $\mathbb{F}_{p^2}^\times$. Each admissible pair $(a,c)$ corresponds to exactly two roots $\alpha$ and $\alpha^p$. Therefore, the number of distinct pairs $(a,c)$ is

$$ \frac{\varphi(p+1)}{2}. $$

Step 5: Exceptional cases

For $p = 2$, $p+1 = 3$. There are $\varphi(3) = 2$ primitive 3rd roots of unity in $\mathbb{F}_4$, forming one conjugate pair. Hence the formula $\varphi(p+1)/2 = 1$ still holds.
$\alpha = \alpha^p$ is impossible for an element of order $p+1>2$, so the 2-to-1 correspondence is valid for all primes $p$.

Step 6: Conclusion

The number of pairs $(a,c) \in \mathbb{F}_p \times \mathbb{F}_p$ satisfying the maximal-period conditions of Exercise 34 is

$$ \boxed{\frac{\varphi(p+1)}{2}}. $$

This correctly accounts for the conjugate roots and the order conditions.

Verification

Each $\alpha$ of exact order $p+1$ satisfies $x^{p+1} \bmod f(x)$ constant nonzero and $x^{(p+1)/q} \bmod f(x)$ of degree 1.
Each polynomial $f(x) = x^2 - c x - a$ corresponds to exactly one pair $(a,c)$, obtained from the conjugate pair ${\alpha, \alpha^p}$.
The total number of admissible pairs is $\varphi(p+1)/2$.

This completes the solution.

∎