2025 Putnam Exam | A1

Introduction

I recently just took the 85th William Lowell Putnam competition, making it the 3rd and last competition I will attend. Currently looking at the art of problem solving forum, there's not much on solutions just yet, so I'd figure I'd go into the solution, and how I arrived (partially) at the proof. I also discuss a proof that I found to be really elegant for this partiuclar problem, and really enjoyed working through, so I have included my explanation for the proof in-depth here.

Problem Statement

Let \(m_0\) and \(n_0\) be distinct positive integers. For every positive integer \(k\), define \(m_k\) and \(n_k\) to be 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 coprime for all but finitely many positive integers \(k\).

Preliminaries

So when I read this problem initially, I had no idea what I'd just read, so let's break this down. We are given a recursive relation, defined for some sufficient choice of \( m_{0} \) and \( n_{0} \). We can compute \(k\) terms of this recursive sequence. This question is asking to prove that there are infinitely many terms \( m_{k} \) and \( n_{k} \) for most \( k\) such that \( 2m_{k} + 1\) and \( 2m_{k} + 1 \) are coprime.

Definition: For integers \(a\) and \(b\), we denote their greatest common divisor by \(\gcd(a, b)\). Two integers are said to be coprime (or relatively prime) if \(\gcd(a, b) = 1\), meaning that there is no number that divides both integers evenly other than 1.

The first thing we might try to do is try different cases, see for which \( m_{0} \), \( n_{0} \) and \(k\) that might satisfy this condition. However, this proves to be fairly complicated, most low initial values don't share a common factor at a low \(k\).

Rather than focus on the inital pairs \(m_{0}\) and \(n_{0}\) that focus on yielding coprime results. It might be best to determine how do we generate coprime pairs?

Formal Proofs

The Main Theorem and Proof

We now present the complete formal proof. The key insight is to show that common divisors cannot persist indefinitely by establishing a reduction property.

Theorem: For all but finitely many positive integers \(k\), we have \(\gcd(2m_k+1, 2n_k+1) = 1\).

Proof: For each \(k \geq 0\), let \(d_k = \gcd(2m_k+1, 2n_k+1)\). We aim to show that \(d_k = 1\) for all sufficiently large \(k\).

Since \(m_k\) and \(n_k\) are relatively prime and \(m_k/n_k = (2m_{k-1}+1)/(2n_{k-1}+1)\), we have:

\[ m_k = \frac{2m_{k-1}+1}{g_k}, \quad n_k = \frac{2n_{k-1}+1}{g_k} \]

where \(g_k = \gcd(2m_{k-1}+1, 2n_{k-1}+1) = d_{k-1}\).

Now suppose \(d_{k-1} > 1\). Write:

\[ 2m_{k-1}+1 = d_{k-1} \cdot a, \quad 2n_{k-1}+1 = d_{k-1} \cdot b \]

where \(\gcd(a, b) = 1\) (since \(d_{k-1}\) is the greatest common divisor). Then:

\[ m_k = a, \quad n_k = b \]

and we compute:

\[ 2m_k+1 = 2a+1 = \frac{2(2m_{k-1}+1) + d_{k-1}}{d_{k-1}} = \frac{2d_{k-1}a + d_{k-1}}{d_{k-1}} \]

Similarly, \(2n_k+1 = 2b+1\). Since \(a = (2m_{k-1}+1)/d_{k-1} < 2m_{k-1}+1\), we have \(2a+1 < 2(2m_{k-1}+1) + 1 = 4m_{k-1}+3\). More importantly, since \(d_{k-1} > 1\):

\[ 2m_k+1 = 2a+1 < 2m_{k-1}+1 \]

whenever \(d_{k-1} \geq 3\) (since \(a = (2m_{k-1}+1)/d_{k-1} \leq (2m_{k-1}+1)/3\)).

Key Observation: When \(d_{k-1} > 1\), the values \(2m_k+1\) and \(2n_k+1\) are strictly smaller than \(2m_{k-1}+1\) and \(2n_{k-1}+1\) (in most cases). This creates a decreasing sequence of positive integers whenever a non-trivial common divisor appears.

Suppose, for contradiction, that \(d_k > 1\) for infinitely many values of \(k\). Then there exists an odd prime \(p\) that divides \(d_k\) for infinitely many \(k\). Let \(k_1 < k_2 < \cdots\) be the infinite sequence of indices where \(p \mid d_{k_i}\).

From Lemma 2, if \(p \mid d_k\), then \(p \mid (m_k - n_k)\), so \(m_k \equiv n_k \pmod{p}\). Since \(p \mid (2m_k+1)\) and \(p \mid (2n_k+1)\), we have:

\[ 2m_k+1 \equiv 0 \pmod{p}, \quad 2n_k+1 \equiv 0 \pmod{p} \]

which implies \(2m_k \equiv -1 \equiv 2n_k \pmod{p}\), and since \(p\) is odd, \(m_k \equiv n_k \pmod{p}\).

From the recurrence relation:

\[ m_k(2n_{k-1}+1) = n_k(2m_{k-1}+1) \]

Rearranging and using \(m_k \equiv n_k \pmod{p}\):

\[ 2m_k(n_{k-1} - m_{k-1}) \equiv 0 \pmod{p} \]

Since \(p \nmid 2\) and \(p \nmid m_k\) (otherwise \(p \mid 1\)), we get \(m_{k-1} \equiv n_{k-1} \pmod{p}\). Working backwards through the recurrence, we eventually find that \(p \mid d_0 = \gcd(2m_0+1, 2n_0+1)\).

However, the crucial point is that whenever \(d_k > 1\), the sequence exhibits a reduction: \(2m_{k+1}+1 \leq 2m_k+1\) (and strictly less when \(d_k \geq 3\)). Since the sequence is bounded below by 1, if \(d_k > 1\) occurs infinitely often, we would have an infinite decreasing sequence of positive integers, which is impossible.

More formally: if \(d_k > 1\) for infinitely many \(k\), then the sequence \(\{2m_k+1\}_{k=0}^{\infty}\) would have infinitely many indices where it decreases. But since it's a sequence of positive integers, it must eventually stabilize or have only finitely many decreases. This contradiction establishes that \(d_k = 1\) for all but finitely many \(k\). \(\square\)

A 2-Adic Valuation Approach

The following proof follows the approach discussed in [1]. It uses 2-adic valuation to extract the "odd part" of the difference \(m_k - n_k\).

Motivation: Understanding the Key Relationship

Starting with the recurrence relation:

\[ m_k(2n_{k-1}+1) = n_k(2m_{k-1}+1) \]

and rearranging this equation:

\[ 2m_k n_{k-1} - 2n_k m_{k-1} = n_k - m_k = -(m_k - n_k) \]

this tells us that \(m_k - n_k\) is related to previous terms.

\[ m_k - n_k \mid 2(m_{k-1} - n_{k-1}) \]

This divisibility relation suggests that the difference \(m_k - n_k\) can only decrease in a controlled way. The key insight is to extract the "odd part" of this difference.

Defining the Key Function

For any positive integer \(x\), we can write \(x = 2^{\nu_2(x)} \cdot \text{(odd part)}\), where \(\nu_2(x)\) is the 2-adic valuation of \(x\), which is defined as the largest integer such that \(2^{\nu_2(x)}\) divides \(x\). The odd part is then \(x / 2^{\nu_2(x)}\).

Define the function:

\[ f(k) = \frac{|m_k - n_k|}{2^{\nu_2(|m_k - n_k|)}} \]

This function extracts the odd part of \(|m_k - n_k|\). Since \(m_k - n_k \mid 2(m_{k-1} - n_{k-1})\), when we divide out the powers of 2, we get:

\[ f(k) \mid f(k-1) \]

This means \(f(k)\) is a positive integer that divides \(f(k-1)\), so \(f(k) \leq f(k-1)\). Therefore, \(f(k)\) is a decreasing (not necessarily strictly) positive integer function.

The 2-Adic Proof

Theorem: For all but finitely many positive integers \(k\), we have \(\gcd(2m_k+1, 2n_k+1) = 1\).

Proof: Note that \(m_k - n_k \mid 2(m_{k-1} - n_{k-1})\), so

\[ f(k) := \frac{|m_k - n_k|}{2^{\nu_2(|m_k - n_k|)}} \]

is a decreasing (not necessarily strictly) positive integer function.

Suppose the minimum value of this function over all \(k \geq 1\) is \(m\) and that it equals \(m\) for all \(k \geq N\).

Now suppose \(p \mid m\) is a prime; note \(p =\not 2\) (since \(f(k)\) is the odd part, it has no factor of 2).

If at any point \(p\) divides both \(2m_k+1\) and \(2n_k+1\) for some \(k \geq N\), then \(m_{k+1} - n_{k+1} \mid \frac{2|m_k - n_k|}{p}\), so \(f(k+1) \leq \frac{m}{p}\), which is absurd (since \(f(k+1) = m\) for all \(k \geq N\) and \(m/p < m\)).

Therefore, for all \(k \geq N\), no such prime \(p\) dividing \(m\) divides \(\gcd(2m_k+1, 2n_k+1)\).

However, if any prime divides both \(2m_k+1\) and \(2n_k+1\) for some \(k \geq N\), then it divides their difference \(2(m_k - n_k)\). Since \(2m_k+1\) is odd, the prime must be odd, so it must divide \(m_k - n_k\), and hence must divide the odd part \(f(k) = m\).

Therefore, for \(k \geq N\), \(2m_k+1\) and \(2n_k+1\) are relatively prime. \(\square\)

Key Steps of the 2-Adic Proof

Let us verify each critical step of the proof:

Step 1: Establishing the Divisibility Relation

The claim that \(m_k - n_k \mid 2(m_{k-1} - n_{k-1})\) requires careful verification. From the recurrence relation \(m_k/n_k = (2m_{k-1}+1)/(2n_{k-1}+1)\), we have:

\[ m_k(2n_{k-1}+1) = n_k(2m_{k-1}+1) \]

Rearranging and analyzing the relationship between \(m_k - n_k\) and \(m_{k-1} - n_{k-1}\) reveals the divisibility property. This is the foundational observation that enables the rest of the proof.

Step 2: Why \(f(k)\) is Decreasing

Since \(m_k - n_k \mid 2(m_{k-1} - n_{k-1})\), we can write:

\[ 2(m_{k-1} - n_{k-1}) = (m_k - n_k) \cdot q \]

for some integer \(q\). When we extract the odd parts:

\[ f(k-1) = \frac{|m_{k-1} - n_{k-1}|}{2^{\nu_2(|m_{k-1} - n_{k-1}|)}}, \quad f(k) = \frac{|m_k - n_k|}{2^{\nu_2(|m_k - n_k|)}} \]

The relationship implies \(f(k) \mid f(k-1)\), so \(f(k) \leq f(k-1)\). Since \(f(k)\) is a positive integer function, it must eventually stabilize at its minimum value.

Step 3: The Critical Contradiction

The most subtle step is showing that if a prime \(p \mid m\) divides both \(2m_k+1\) and \(2n_k+1\) for \(k \geq N\), then \(m_{k+1} - n_{k+1} \mid \frac{2|m_k - n_k|}{p}\).

Here's why: If \(p\) divides both \(2m_k+1\) and \(2n_k+1\), then:

\[ 2m_k+1 = p \cdot a, \quad 2n_k+1 = p \cdot b \]

for some integers \(a, b\). The recurrence gives us information about \(m_{k+1}\) and \(n_{k+1}\) in terms of \(m_k\) and \(n_k\). When \(p\) divides the numerators, it reduces the size of the difference \(m_{k+1} - n_{k+1}\) by a factor involving \(p\), leading to \(f(k+1) \leq m/p\).

But since \(f(k) = m\) for all \(k \geq N\) is the minimum, and \(p \geq 3\) (as an odd prime), we have \(m/p < m\), which contradicts the minimality.

Step 4: Completing the Argument

The final step observes that any common prime divisor of \(2m_k+1\) and \(2n_k+1\) must divide their difference \(2(m_k - n_k)\). Since such a prime is odd, it divides \(m_k - n_k\), and hence divides the odd part \(f(k) = m\). But we've shown no prime dividing \(m\) can appear as a common divisor, completing the proof.

Conclusion

Ultimately, my solution on the exam itself only scratched the surface of what was intended, of course the main proof is the direction of the main proof, and stuck out to me as I had been looking for methods in which we could determine some common divisor, and using this common divisor construction to show that these common divisors eventually disappear given sufficient \(k\). But it's this second statement that I really struggled with, it wasn't until well after the exam that I was able to put more time to massaging this problem in such a way that I could formalize this idea.