Putnam 2025, Problem B-3

Suppose \( S \) is a nonempty set of positive integers with the property that if \( n \) is in \( S \), then every positive divisor of \( 2025^n - 15^n \) is in \( S \). Must \( S \) contain all positive integers?

Solution:
Yes, \( S \) must contain all positive integers.

**First solution.** We prove that \( n \in S \) by strong induction on \( n \). We have \( 1 \in S \) because \( S \) is nonempty and 1 divides \( 2025^n - 15^n \) for every \( n \in S \). Now suppose that \( n > 1 \) and \( 1, \ldots, n - 1 \in S \). Write \( n = 3^a 5^b d \) with \( a, b \geq 0 \) and \( \gcd(15, d) = 1 \), and define \( c = \max(a, b) \). Since \( d \) is coprime to 135, we have \( 135^k \equiv 1 \pmod{d} \) for any \( k \) divisible by \( \phi(d) \) (writing \( \phi \) for the Euler totient function). If \( c > 0 \), then \( (3^c - 1)d \geq cd \geq c \), yielding
\[
\phi(d) \leq d < 3^c d - c \leq n - c
\]
and so \( c < n - \phi(d) \); the same holds for \( c = 0 \) because \( \phi(d) \leq \phi(n) < n \) for \( n > 1 \). Consequently, for
\[
k := \phi(d) \lfloor (n - 1)/\phi(d) \rfloor > n - 1 - \phi(d) \geq c,
\]
\( n \) divides \( 15^k (135^k - 1) = 2025^k - 15^k \) and so \( n \in S \).

**Second solution.** (suggested by Evan Dummit) Define the sequence \( \{a_i\} \) by
\[
a_0 = 1, a_{i+1} = 2025^{a_i} - 15^{a_i} \quad (i \geq 0).
\]
By induction on \( i \), \( a_i \) divides \( a_{i+1} \): this is obvious for \( i = 0 \), while for the induction step we apply the identity
\[
x^{md} - y^{md} = (x^m - y^m)(x^{m(d-1)} + \cdots + y^{m(d-1)})
\]
to see that if \( a_i \) divides \( a_{i+1} \), then \( 2025^{a_i} - 15^{a_i} \) divides \( 2025^{a_{i+1}} - 15^{a_{i+1}} \).

We prove that every positive integer divides some \( a_i \). Suppose by way of contradiction that this fails, and let \( n \) be the smallest positive integer not dividing any \( a_i \). This \( n \) cannot equal 1. Let \( p \) be the smallest prime factor of \( n \), and write \( n = p^e m \) with \( m \) coprime to \( p \); then \( m < n \) and so \( m \) divides some \( a_i \) (by the previous paragraph). If \( p^e < n \) then \( p^e \) also divides all sufficiently large \( a_i \), as then does \( \text{lcm}(p^e, m) = n \), a contradiction; hence \( n = p^e \) is a prime power. We cannot have \( p = 3 \) or \( p = 5 \) because the \( a_i \) tend to \( \infty \) and \( a_{i+1} \) is divisible by \( 15^{a_i} \); hence \( n \) is coprime to 135. Since \( \phi(n) < n \), \( \phi(n) \) must divide some \( a_i \); but now \( n \) divides \( 135^{a_i} - 1 \) and hence also \( a_{i+1} \), again a contradiction.