Putnam 2025, Problem B-5

Let \( p \) be a prime number greater than 3. For each \( k \in \{1, \ldots, p - 1\} \), let \( I(k) \in \{1, 2, \ldots, p - 1\} \) be such that \( k \cdot I(k) \equiv 1 \pmod{p} \). Prove that the number of integers \( k \in \{1, \ldots, p - 2\} \) such that \( I(k + 1) < I(k) \) is greater than \( p/4 - 1 \).

Solution:
Let \( f(p) \) denote the number of \( k \in \{1, \ldots, p - 2\} \) such that \( I(k + 1) < I(k) \). We prove that \( f(p) > \frac{p}{4} - 1 \) for \( p > 3 \) by deriving an exact formula for \( f(p) \).

In the field \( \mathbb{F}_p \) we have the identity
\[
\frac{1}{k + 1} + \frac{1}{1/k + 1} = 1 \quad (k \neq -1).
\]
This implies that for \( k = 1, \ldots, p - 2 \),
\[
I(k + 1) + I(I(k) + 1) = p + 1 :
\]
the left-hand side is congruent to 1 modulo \( p \), but each summand is in \( \{1, \ldots, p - 1\} \) so the sum lies strictly between 1 and \( 2p + 1 \).

Since we cannot have \( I(k + 1) = I(k) \), we can interpret \( f(p) \) as the number of \( k \in \{1, \ldots, p - 2\} \) such that \( I(k + 1) < I(k) + 1 \), or equivalently
\[
I(k) + 1 + I(I(k) + 1) > p + 1.
\]
Set \( m := I(k) + 1 \); as \( k \) runs over \( \{1, \ldots, p - 2\} \), \( I(k) \) also runs over \( \{1, \ldots, p - 2\} \) (because \( I(p - 1) = p - 1 \)) and so \( m \) runs over \( \{2, \ldots, p - 1\} \). Consequently, \( f(p) \) counts \( m \in \{2, \ldots, p - 1\} \) such that
\[
m + I(m) > p + 1,
\]
or equivalently \( m \in \{1, \ldots, p - 1\} \) since \( m = 1 \) never satisfies the condition.

By writing \( I(p - m) = p - I(m) \), we see that
\[
p - m + I(p - m) = 2p - (m + I(m)).
\]
Consequently, exactly one of \( m + I(m) > p + 1 \) or \( p - m + I(p - m) > p + 1 \) holds unless \( m + I(m) \in \{p - 1, p, p + 1\} \). By symmetry, \( f(p) \) equals \( \frac{p - 1}{2} \) minus half the number of \( m \in \{1, \ldots, p - 1\} \) with \( m + I(m) \in \{p - 1, p, p + 1\} \).

Since \( p > 3 \), \( m + I(m) = p \pm 1 \) if and only if \( m^2 \pm m + 1 = 0 \) in \( \mathbb{F}_p \); for each sign, we get 2 solutions if \( p \equiv 1 \pmod{3} \) and 0 otherwise. Similarly, \( m + I(m) = p \) if and only if \( m^2 + 1 = 0 \) in \( \mathbb{F}_p \); we get 2 solutions if \( p \equiv 1 \pmod{4} \) and 0 otherwise. Hence \( f(p) \) equals
\[
\frac{p - 1}{2} - (2 \text{ if } p \equiv 1 \pmod{3}) - (1 \text{ if } p \equiv 1 \pmod{4}).
\]
In particular, \( f(p) - (\frac{p}{4} - 1) \geq \frac{p - 1}{2} - 2 - \frac{p}{4} = \frac{p - 10}{4} \). This proves the claim for \( p \geq 11 \); for \( p = 5, 7 \) we compute directly that \( f(p) = 1 > \frac{p}{4} - 1 \).