Maths Olympiad Prep

Library / Singapore Mathematical Olympiad (SMO) /45 of 52

Singapore Mathematical Olympiad (SMO)

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 50≥∣a∣≥∣b∣≥∣c∣≥150 \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 u∣pu \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 2≤502 \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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