Putnam 2013, Problem A-2

Let \( S \) be the set of all positive integers that are not perfect squares. For \( n \in S \), consider choices of integers \( a_1, a_2, \ldots, a_r \) such that \( n < a_1 < a_2 < \cdots < a_r \) and \( n \cdot a_1 \cdot a_2 \cdots a_r \) is a perfect square, and let \( f(n) \) be the minimum of \( a_r \) over all such choices. Show that the function \( f \) from \( S \) to the integers is one-to-one.

Solution:
Suppose to the contrary that $f(n) = f(m)$ with $n < m$, and let $n \cdot a_1 \cdots a_r$, $m \cdot b_1 \cdots b_s$ be perfect squares where $n < a_1 < \cdots < a_r$, $m < b_1 < \cdots < b_s$, $a_r = b_s$. Then $(n \cdot a_1 \cdots a_r) \cdot (m \cdot b_1 \cdots b_s)$ is also a perfect square. Now eliminate any factor in this product that appears twice (i.e., if $a_i = b_j$ for some $i,j$, then delete $a_i$ and $b_j$ from this product). The product of what remains must also be a perfect square, but this is now a product of distinct integers, the smallest of which is $n$ and the largest of which is strictly smaller than $a_r = b_s$. This contradicts the minimality of $a_r$.

**Remark:** Sequences whose product is a perfect square occur naturally in the quadratic sieve algorithm for factoring large integers. However, the behavior of the function $f(n)$ seems to be somewhat erratic. Karl Mahlburg points out the upper bound $f(n) \leq 2n$ for $n \geq 5$, which holds because the interval $(n,2n)$ contains an integer of the form $2m^2$. A trivial lower bound is $f(n) \geq n + p$ where $p$ is the least prime factor of $n$. For $n = p$ prime, the bounds agree and we have $f(p) = 2p$. For more discussion, see https://oeis.org/A006255.