Maths Olympiad Prep

Library / /49 of 56

Number theory Difficulty 6.4 National Olympiad Prove it Singapore

Let aa, bb, cc be nonzero integers, with 11 as their only positive common divisor, such that 1a+1b+1c=0\frac{1}{a} + \frac{1}{b} + \frac{1}{c} = 0. Find the number of such triples (a,b,c)(a, b, c) with 50abc150 \geq |a| \geq |b| \geq |c| \geq 1.

Solution

Since the sum is 00, there are positive and negative integers among the three. Without loss of generality, we assume that there is 11 negative and two positive integers. (The other case is obtained by changing the signs of all the integers.) Then c<0c < 0 since it has the smallest absolute value. Let gcd(a,b)=p\gcd(a, b) = p, gcd(b,c)=q\gcd(b, c) = q and gcd(a,c)=r\gcd(a, c) = r. Then gcd(p,q)=gcd(q,r)=gcd(r,p)=1\gcd(p, q) = \gcd(q, r) = \gcd(r, p) = 1. Therefore a=prsa = pr s, b=pqtb = pq t and c=qrc = -qr for some integers ss, tt, uu with gcd(s,t)=gcd(s,u)=gcd(t,u)=1\gcd(s, t) = \gcd(s, u) = \gcd(t, u) = 1. Substitute into the original equation and simplify, we have
qt+rs=pstu. qt + rs = \frac{pst}{u}.
Now, uu has no common factor with ss and tt. Thus upu \mid p. This means uu is a common divisor of aa, bb, cc. By our assumption, u=1u = 1. By symmetry, we also have s=t=1s = t = 1. Therefore q+r=pq + r = p and a=pra = pr, b=pqb = pq, c=qrc = -qr. Thus every triple pp, qq, rr, pairwise coprime with q+r=pq + r = p uniquely determines the triple aa, bb, cc. We have the following triples, with the product of the larger 2502 \leq 50:
(1,2,3),(1,3,4),(1,4,5),(1,5,6),(1,6,7),(2,3,5),(2,5,7),(3,4,7),(3,5,8),(4,5,9). (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (1, 6, 7), (2, 3, 5), (2, 5, 7), (3, 4, 7), (3, 5, 8), (4, 5, 9).
Therefore, we have 2020 such triples.

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.