Olympiad Maths Prep

Track / Stage 7 / 5 of 300 #1405 of 2000

Problem 1405

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.0 Prove it

Prove that there exists an integer n1n \geq 1, such that number of all pairs (a,b)(a, b) of positive integers, satisfying 1ab1a+1b=1n\frac{1}{a-b}-\frac{1}{a}+\frac{1}{b}=\frac{1}{n} exceeds 2024.2024.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Rearrange the given equation:
1ab1a+1b=1n \frac{1}{a-b} - \frac{1}{a} + \frac{1}{b} = \frac{1}{n}
To:
b(ab)a(ab)+abab(ab)=1n \frac{b(a-b) - a(a-b) + ab}{ab(a-b)} = \frac{1}{n}
Simplifying the numerator:
b(ab)a(ab)+ab=abb2a2+ab+ab=3aba2b2 b(a-b) - a(a-b) + ab = ab - b^2 - a^2 + ab + ab = 3ab - a^2 - b^2
Thus, the equation becomes:
3aba2b2ab(ab)=1n \frac{3ab - a^2 - b^2}{ab(a-b)} = \frac{1}{n}
Rearranging gives:
n(3aba2b2)=ab(ab) n(3ab - a^2 - b^2) = ab(a-b)
Simplifying further:
n(a2ab+b2)=ab(ab) n(a^2 - ab + b^2) = ab(a-b)

2. **Set a=da1a = da_1 and b=db1b = db_1 where d=gcd(a,b)d = \gcd(a, b):**
n(d2(a12a1b1+b12))=d2a1b1(a1b1) n(d^2(a_1^2 - a_1b_1 + b_1^2)) = d^2a_1b_1(a_1 - b_1)
Dividing both sides by d2d^2:
n(a12a1b1+b12)=a1b1(a1b1) n(a_1^2 - a_1b_1 + b_1^2) = a_1b_1(a_1 - b_1)

3. Analyze the gcd condition:
gcd(a12a1b1+b12,a1b1)=1 \gcd(a_1^2 - a_1b_1 + b_1^2, a_1b_1) = 1
If pp is a prime dividing both a12a1b1+b12a_1^2 - a_1b_1 + b_1^2 and a1b1a_1 - b_1, then:
a1b1(modp) a_1 \equiv b_1 \pmod{p}
Substituting a1b1(modp)a_1 \equiv b_1 \pmod{p} into a12a1b1+b12a_1^2 - a_1b_1 + b_1^2:
a12a12+a120(modp) a_1^2 - a_1^2 + a_1^2 \equiv 0 \pmod{p}
Thus, pa1,b1p \mid a_1, b_1, which is a contradiction.

4. **Find \ell such that:**
d=(a12a1b1+b12)andn=a1b1(a1b1) d = \ell(a_1^2 - a_1b_1 + b_1^2) \quad \text{and} \quad n = \ell a_1b_1(a_1 - b_1)

5. **Consider primes p1<p2<<pLp_1 < p_2 < \cdots < p_L where L2024L \gg 2024:**
n=1iLpi(pi1) n = \prod_{1 \le i \le L} p_i(p_i - 1)
For a1=pia_1 = p_i and b1=1b_1 = 1:
=jpj(pj1)pi(pi1) \ell = \frac{\prod_j p_j(p_j - 1)}{p_i(p_i - 1)}
This generates at least LL distinct pairs (a,b)(a, b).

6. Conclusion:
Since LL can be chosen to be greater than 2024, there exists an integer n1n \geq 1 such that the number of pairs (a,b)(a, b) satisfying the given equation exceeds 2024.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.