Sharpen Your Pencils

Putnam Mathematical Competition Problem B3

Suppose S is a nonempty set of positive integers with the property that if n is in S, then every positive divisor of 2025ⁿ−15ⁿ is in S. Must S contain all positive integers?

Answer:

Yes.

Solution:

First note that 2025/15 = 135 = 3³·5, so that 2025_ⁿ − 15ⁿ = 15ⁿ(135ⁿ − 1). If n is in S, then S contains all divisors of 2025_ⁿ − 15ⁿ, which include 1, 2, and 3. We show by induction that S contains all positive integers. For the inductive step, suppose all integers less than n are in S, and let n = 3^a5^bc, where c is relatively prime to 15. By Euler’s theorem (or by the pigeonhole principle), there exists k with 1 ≤ k ≤ c−1 such that c divides 135^k − 1. If a = b = 0, we are done. If a + b > 0, then by, say, an easy induction or the tangent line approximation to f(x) = y^x at x = 0, one sees that a < 3^a and b < 5^b, implying

a + b < 3^a + 5^b − 1 = 3^a5^b + (3^a − 1) (5^b − 1) ≤ 3^a5^b.

Hence

(a + b)k ≤ 3^a5^b(c − 1) < n,

c divides 135^(a+b)k − 1, and 3^a5^b divides 15^(a+b)k, so that n divides 2025^(a+b)k −15^(a+b)k.

Therefore, n is in S.