Putnam 2025, Problem A-1

Let \( m_0 \) and \( n_0 \) be distinct positive integers. For every positive integer \( k \), define \( m_k \) and \( n_k \) to be the relatively prime positive integers such that
\[
\frac{m_k}{n_k} = \frac{2m_{k-1} + 1}{2n_{k-1} + 1}.
\]
Prove that \( 2m_k + 1 \) and \( 2n_k + 1 \) are relatively prime for all but finitely many positive integers \( k \).

Solution:
For each \( k \geq 0 \), the numbers \( 2m_k + 1 \) and \( 2n_k + 1 \) are odd, so their greatest common factor \( d_k \) must be odd. For an integer \( r \), let \( \text{Odd}(r) \) denote the largest odd factor of \( r \). Then note that
\[
\text{Odd}(m_{k+1} - n_{k+1}) = \text{Odd}\left( \frac{2m_k + 1}{d_k} - \frac{2n_k + 1}{d_k} \right) = \text{Odd}\left( \frac{m_k - n_k}{d_k} \right) \leq \text{Odd}(m_k - n_k),
\]
with equality if and only if \( d_k = 1 \). Thus \( \text{Odd}(m_k - n_k) \) is a nonincreasing sequence of positive integers, decreasing only when \( d_k > 1 \). Hence the sequence \( \text{Odd}(m_k - n_k) \) must stabilize once \( k \) is greater than some \( K \), implying that \( d_k = 1 \) for \( k > K \); that is, \( 2m_k + 1 \) and \( 2n_k + 1 \) are relatively prime for all \( k > K \), as desired.