Maths Olympiad Prep

Library / /12 of 299

Number theory Difficulty 5.1 AIME, harder Prove it Iran

Prove that for every positive integer nn, one can find three pairwise coprime positive integers a,b,c>na, b, c > n such that the set of prime divisors of a+b+ca + b + c and ab+ac+bcab + ac + bc are the same.

Solution

We seek for large enough positive integers a,b,ca, b, c such that ab+ac+bca+b+c=3N\frac{ab+ac+bc}{a+b+c} = 3^N for some positive integer NN. Indeed, one can write ab+ac+bca+b+c=a+ba2+ab+b2a+b+c\frac{ab+ac+bc}{a+b+c} = a+b-\frac{a^2+ab+b^2}{a+b+c}. Now, choose cc such that a2+ab+b2a+b+c=1\frac{a^2+ab+b^2}{a+b+c} = 1 that is, c=a2+b2+ababc = a^2+b^2+ab-a-b then we need to find a,ba, b such that a+b1=3Na+b-1=3^N. Choose coprime a,ba, b such that 33 doesn't divide ab(a1)(b1)ab(a-1)(b-1) it follows that gcd(c,b)=gcd(c,a)=1\text{gcd}(c, b) = \text{gcd}(c, a) = 1. Further, choosing ab2(mod3)a \equiv b \equiv 2 \pmod{3} implies that 33 divides also a+b+c=a2+ab+b2a+b+c = a^2+ab+b^2. The rest is clear.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.