Maths Olympiad Prep

Library / /542 of 860

Number theory Difficulty 5.3 AIME, harder Find the answer

Compute the number of integers n{1,2,,300}n \in\{1,2, \ldots, 300\} such that nn is the product of two distinct primes, and is also the length of the longest leg of some nondegenerate right triangle with integer side lengths.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n=pqn=p \cdot q for primes p<qp<q. If nn is the second largest side of a right triangle there exist integers c,ac, a such that a<pqa<p q and (pq)2=c2a2=(ca)(c+a)(p q)^{2}=c^{2}-a^{2}=(c-a)(c+a). Since ca<c+ac-a<c+a there are three cases for the values of ca,c+ac-a, c+a, and in each case we determine when a<pqa<p q. (a) ca=1c-a=1 and c+a=p2q2c+a=p^{2} q^{2} : Then a=p2q212>pqa=\frac{p^{2} q^{2}-1}{2}>p q, so there are no solutions. (b) ca=pc-a=p and c+a=pq2c+a=p q^{2} : Then a=pq2p2>pqa=\frac{p q^{2}-p}{2}>p q. (c) ca=p2c-a=p^{2} and c+a=q2c+a=q^{2}. Then a=q2p22a=\frac{q^{2}-p^{2}}{2} which we require to be less than pqp q. This is equivalent to q2p22<pqq2<2pq+p22q2<(q+p)22q<q+p(21)q<p<q\frac{q^{2}-p^{2}}{2} <p q q^{2} <2 p q+p^{2} 2 q^{2} <(q+p)^{2} \sqrt{2} q <q+p (\sqrt{2}-1) q <p<q. So the problem is equivalent to finding the number of distinct prime pairs (p,q)(p, q) such that pq<300p q<300 and (21)q<p<q(\sqrt{2}-1) q<p<q. There are 13 such pairs: {(3,5),(3,7),(5,7),(5,11),(7,11),(7,13),(11,13),(11,17),(11,19),(11,23),(13,17),(13,19),(13,23)}\{(3,5),(3,7),(5,7),(5,11),(7,11),(7,13),(11,13),(11,17),(11,19),(11,23),(13,17),(13,19),(13,23)\} and 1323=29913 \cdot 23=299 which is the biggest such pair. The most interesting borderline case are (3,7):37.42>21(3,7): \frac{3}{7} \approx .42>\sqrt{2}-1, which leads to the (20,21,29)(20,21,29) triangle, (5,13):513.385<21(5,13): \frac{5}{13} \approx .385<\sqrt{2}-1, which leads to the (65,72,97)(65,72,97) triangle, and (7,17):717.411<21(7,17): \frac{7}{17} \approx .411<\sqrt{2}-1 which leads to the (119,120,169)(119,120,169) right triangle.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.