Maths Olympiad Prep

Library / /34 of 91

, 2006

Number theory Difficulty 5.6 AIME, harder Prove it India

Find all triples (a,b,c)(a, b, c) integers such that a2+b2=c2a^2 + b^2 = c^2, gcd(a,b,c)=1\text{gcd}(a, b, c) = 1 and 2000a,b,c30002000 \le a, b, c \le 3000.

Solution

We use the known characterisation of primitive Pythagorean triples (a,b,c)(a, b, c): a=2pqa = 2pq, b=p2q2b = p^2 - q^2, c=p2+q2c = p^2 + q^2, where pp and qq are relatively prime integers, one even and q<pq < p. The given condition entails c2=a2+b2>2×20002c^2 = a^2 + b^2 > 2 \times 2000^2. Hence 20002<c=p2+q2<30002000\sqrt{2} < c = p^2 + q^2 < 3000. Using the approximation 2=1.4142\sqrt{2} = 1.4142, we get 2828<p2+q2<30002828 < p^2 + q^2 < 3000. We also have 2000<b=p2q22000 < b = p^2 - q^2. Adding these two, we obtain 4828<2p24828 < 2p^2, whence 50p50 \le p. Again, we have 2000<a=2pq2000 < a = 2pq. Subtracting this from p2+q2<3000p^2+q^2 < 3000, we get (pq)2<1000(p-q)^2 < 1000 giving pq31p-q \le 31. Using 50p50 \le p and pq31p-q \le 31, we obtain 19q19 \le q and hence 3000>p2+q2p2+1923000 > p^2+q^2 \ge p^2+19^2. It follows that p2<2639p^2 < 2639 and thus p51p \le 51. We obtain 2000/51<2pq/p=2q2000/51 < 2pq/p = 2q.

We thus obtain a better bound for qq: 20q20 \le q and hence a better bound for pp: p2<2639p^2 < 2639 and hence p50p \le 50. We have seen earlier that p50p \ge 50, thus getting p=50p = 50. Using p2+q2<3000p^2 + q^2 < 3000, we now get q2<500q^2 < 500. This implies that q22q \le 22. Thus 20q2220 \le q \le 22. However qq has to be odd since pp is even. We conclude that q=21q = 21. We see that a=2100a = 2100, b=2059b = 2059 and c=2941c = 2941 give only one triple in the given range.

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.