Maths Olympiad Prep

Library / /63 of 86

Number theory Difficulty 7.3 National Olympiad, round 2 Prove it United States

Problem:

a. Find two quadruples of positive integers (a,b,c,n)(a, b, c, n), each with a different value of nn greater than 33, such that
ab+bc+ca=n \frac{a}{b} + \frac{b}{c} + \frac{c}{a} = n

b. Show that if a,b,ca, b, c are nonzero integers such that ab+bc+ca\frac{a}{b} + \frac{b}{c} + \frac{c}{a} is an integer, then abca b c is a perfect cube. (A perfect cube is a number of the form n3n^3, where nn is an integer.)

Solution

Solution:

a.
For example, (1,2,4,5)(1, 2, 4, 5) and (9,2,12,6)(9, 2, 12, 6) work.

b.
Before solving the problem, we establish a useful definition and lemma.

If pp is a prime and xx is a nonzero rational number, we define ordpx\operatorname{ord}_p x to be the unique integer kk such that pkxp^{-k} x is an integer not divisible by pp. For example, ord345=2\operatorname{ord}_3 45 = 2 and ord5115=1\operatorname{ord}_5 \frac{11}{5} = -1. Then we claim the following:

Lemma. Let pp be prime and let x,yx, y be nonzero rational numbers. Then:

(i) ordp(xy)=ordpx+ordpy\operatorname{ord}_p(xy) = \operatorname{ord}_p x + \operatorname{ord}_p y.

(ii) ordp(x/y)=ordpxordpy\operatorname{ord}_p(x / y) = \operatorname{ord}_p x - \operatorname{ord}_p y.

(iii) If ordpx<ordpy\operatorname{ord}_p x < \operatorname{ord}_p y, then ordp(x+y)=ordpx\operatorname{ord}_p(x + y) = \operatorname{ord}_p x.

Proof of the lemma. Parts (i)-(ii) are straightforward. For part (iii), let k=ordpxk = \operatorname{ord}_p x and k+=ordpyk + \ell = \operatorname{ord}_p y, where we assume >0\ell > 0. Then pkx=np^{-k} x = n and pky=mp^{-k-\ell} y = m for some integers m,nm, n not divisible by pp. It follows that pk(x+y)=n+pmp^{-k}(x + y) = n + p^{\ell} m, and this is an integer not divisible by pp. Thus ordp(x+y)=k\operatorname{ord}_p(x + y) = k as claimed, proving the lemma.

Now we turn to the problem.

Suppose a,b,ca, b, c are integers such that a/b+b/c+c/aa / b + b / c + c / a is an integer. We will show that ordp(abc)\operatorname{ord}_p(a b c) is a multiple of 33 for all primes pp, which implies that abca b c is a perfect cube.

Let pp be a prime and let r=ordpar = \operatorname{ord}_p a, s=ordpbs = \operatorname{ord}_p b, t=ordpct = \operatorname{ord}_p c. By part (i) of the lemma, ordp(abc)=r+s+t\operatorname{ord}_p(a b c) = r + s + t.

By part (ii) of the lemma, we have ordp(a/b)=rs\operatorname{ord}_p(a / b) = r - s, ordp(b/c)=st\operatorname{ord}_p(b / c) = s - t, and ordp(c/a)=tr\operatorname{ord}_p(c / a) = t - r. If these three differences are 00, then r=s=tr = s = t and r+s+tr + s + t is trivially a multiple of 33. Otherwise, the least of rs,st,trr - s, s - t, t - r is negative and the greatest is positive (since their sum is 00).

We now claim that at least two of rs,st,trr - s, s - t, t - r must be tied for least. If this is not true, then, by applying part (iii) of the lemma, we may conclude that ordp(a/b+b/c+c/a)=min{rs,st,tr}<0\operatorname{ord}_p(a / b + b / c + c / a) = \min \{ r - s, s - t, t - r \} < 0, which contradicts the assumption that a/b+b/c+c/aa / b + b / c + c / a is an integer. Thus we have proven our claim. But if two of rs,st,trr - s, s - t, t - r are equal, then r,s,tr, s, t (in some order) form an arithmetic progression, and r+s+tr + s + t is three times the middle term of the progression. Thus we have shown that r+s+tr + s + t is a multiple of 33; in other words, ordp(abc)\operatorname{ord}_p(a b c) is a multiple of 33 for all primes pp, and we are finished.

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.