Putnam 2024, Problem A-4

Find all primes \( p > 5 \) for which there exists an integer \( a \) and an integer \( r \) satisfying \( 1 \leq r \leq p-1 \) with the following property: the sequence \( 1, a, a^2, \ldots, a^{p-5} \) can be rearranged to form a sequence \( b_0, b_1, b_2, \ldots, b_{p-5} \) such that \( b_n - b_{n-1} - r \) is divisible by \( p \) for \( 1 \leq n \leq p-5 \).

Solution:
The prime $p = 7$ works: choose $a = 5$ and $r = 3$, and note that $1,a,a^2$ can be rearranged to form $b_0 = 5, b_1 = 1, b_2 = 25$ satisfying the stated property.

We claim that no prime $p > 7$ works. Suppose otherwise: there exist $p,a,r$ with $p > 7$ and $r \nmid p$ such that $1,a,\ldots,a^{p-5}$ can be rearranged to form $b_0,\ldots,b_{p-5}$ with $b_n \equiv b_0 + nr \pmod{p}$ for all $0 \leq n \leq p-5$. Since $r \nmid p$, $\{b_0,b_0 + r,\ldots,b_0 + (p-5)r\}$ represents a collection of $p-4$ distinct elements of $\mathbb{Z}/p\mathbb{Z}$. It follows that all of $1,a,\ldots,a^{p-5}$ are distinct mod $p$. In particular, $p \nmid a$; also, since $p-5 \geq \frac{p-1}{2}$, we conclude that $a^k \not\equiv 1 \pmod{p}$ for any $1 \leq k \leq \frac{p-1}{2}$. It follows that $a$ is a primitive root mod $p$.

Since $a$ is a primitive root, $a^{-3},a^{-2},a^{-1},a^0,\ldots,a^{p-5}$ runs through all nonzero elements of $\mathbb{Z}/p$ exactly once. On the other hand, $b_0 - 4r,b_0 - 3r,b_0 - 2r,b_0 - r,b_0,\ldots,b_0 + (p-5)r$ runs through all elements of $\mathbb{Z}/p\mathbb{Z}$ exactly once. The given condition now implies that
$$\{b_0 - 4r,b_0 - 3r,b_0 - 2r,b_0 - r\} = \{0,c,c^2,c^3\}$$
where $c = a^{-1}$; that is, $0,c,c^2,c^3$ can be rearranged to give an arithmetic sequence $x_1,x_2,x_3,x_4$ in $\mathbb{Z}/p\mathbb{Z}$.

If $0,c,c^2,c^3$ can be arranged into a four-term arithmetic progression, then by dividing the progression by $c$, we see that $0,1,c,c^2$ can also be arranged into a four-term arithmetic progression. Now no two of $1,c,c^2$ can both be adjacent to $0$ in this arithmetic progression, or otherwise they would be negative of each other; but this is impossible because the order of $c$ is greater than $4$. We conclude that $0$ must be either the first or the last term of the progression, and by reversing the sequence if necessary, we can assume that $0$ is the first term of the progression. Now the last three terms of this progression cannot be $1,c,c^2$ or $c^2,c,1$ in that order, as $c-1 \neq c^2 - c$ because $c \neq 1$. Thus the only possibilities for the arithmetic progression that remain are
$$0,1,c^2,c; \quad 0,c^2,1,c;$$
$$0,c,1,c^2; \quad 0,c,c^2,1.$$

As twice the second term must be the third term, and thrice the second term must be the fourth term, we immediately eliminate each of the above possibilities: the first sequence is not possible because we must have $c^2 = 2, c = 3$, which is a valid solution only when $p = 7$; for the second sequence, we must have $1 = 2c^2$ and $1 = 3c$, which is again a valid solution only when $p = 7$; for the third sequence, we must have $1 = 2c$ and $c^2 = 3c$, implying $c = 1/2 = 3$, which is possible only when $p = 5$; and for the fourth sequence, we must have $c^2 = 2c$ and $1 = 3c$, implying $c = 2 = 1/3$, which is again possible only when $p = 5$.