Putnam 2022, Problem A-3

Let $p$ be a prime number greater than $5$. Let $f(p)$ denote the number of infinite sequences $a_1, a_2, a_3, \ldots$ such that $a_n \in \{1, 2, \ldots, p-1\}$ and $a_n a_{n+2} \equiv 1 + a_{n+1} \pmod{p}$ for all $n \geq 1$. Prove that $f(p)$ is congruent to $0$ or $2 \pmod{5}$.

Solution:
First solution. We view the sequence \( a_1, a_2, \ldots \) as lying in \( \mathbb{F}_p^\times \subset \mathbb{F}_p \). Then the sequence is determined by the values of \( a_1 \) and \( a_2 \), via the recurrence \( a_{n+2} = (1 + a_{n+1})/a_n \). Using this recurrence, we compute  
\[
a_3 = \frac{1 + a_2}{a_1}, \quad a_4 = \frac{1 + a_1 + a_2}{a_1 a_2}, \quad a_5 = \frac{1 + a_1}{a_2}, \quad a_6 = a_1, \, a_7 = a_2
\]  
and thus the sequence is periodic with period 5. The values for \( a_1 \) and \( a_2 \) may thus be any values in \( \mathbb{F}_p^\times \) provided that \( a_1 \neq p - 1 \), \( a_2 \neq p - 1 \), and \( a_1 + a_2 \neq p - 1 \). The number of choices for \( a_1, a_2 \in \{1, \ldots, p - 2\} \) such that \( a_1 + a_2 \neq p - 1 \) is thus \( (p - 2)^2 - (p - 2) = (p - 2)(p - 3) \).  

Since \( p \) is not a multiple of 5, \( (p - 2)(p - 3) \) is a product of two consecutive integers \( a, a + 1 \), where \( a \not\equiv 2 \pmod{5} \). Now \( 0 \cdot 1 \equiv 0 \), \( 1 \cdot 2 \equiv 2 \), \( 3 \cdot 4 \equiv 2 \), and \( 4 \cdot 0 \equiv 0 \pmod{5} \). Thus the number of possible sequences \( a_1, a_2, \ldots \) is 0 or 2 (mod 5), as desired.  

Second solution. Say that a sequence is *admissible* if it satisfies the given conditions. As in the first solution, any admissible sequence is 5-periodic.  

Now consider the collection \( S \) of possible 5-tuples of numbers mod \( p \) given by \( (a_1, a_2, a_3, a_4, a_5) \) for admissible sequences \( \{a_n\} \). Each of these 5-tuples in \( S \) comes from a unique admissible sequence, and there is a 5-periodic action on \( S \) given by cyclic permutation: \( (a, b, c, d, e) \to (b, c, d, e, a) \). This action divides \( S \) into finitely many orbits, and each orbit either consists of 5 distinct tuples (if \( a, b, c, d, e \) are not all the same) or 1 tuple \( (a, a, a, a, a) \). It follows that the number of admissible sequences is a multiple of 5 plus the number of constant admissible sequences.  

Constant admissible sequences correspond to nonzero numbers \( a \pmod{p} \) such that \( a^2 \equiv 1 + a \pmod{p} \). Since the quadratic \( x^2 - x - 1 \) has discriminant 5, for \( p > 5 \) it has either 2 roots (if the discriminant is a quadratic residue mod \( p \)) or 0 roots mod \( p \).