Number theoryDifficulty 5.3AIME, harderFind the answer
Compute the number of integers n∈{1,2,…,300} such that n 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=p⋅q for primes p<q. If n is the second largest side of a right triangle there exist integers c,a such that a<pq and (pq)2=c2−a2=(c−a)(c+a). Since c−a<c+a there are three cases for the values of c−a,c+a, and in each case we determine when a<pq. (a) c−a=1 and c+a=p2q2 : Then a=2p2q2−1>pq, so there are no solutions. (b) c−a=p and c+a=pq2 : Then a=2pq2−p>pq. (c) c−a=p2 and c+a=q2. Then a=2q2−p2 which we require to be less than pq. This is equivalent to 2q2−p2<pqq2<2pq+p22q2<(q+p)22q<q+p(2−1)q<p<q. So the problem is equivalent to finding the number of distinct prime pairs (p,q) such that pq<300 and (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)} and 13⋅23=299 which is the biggest such pair. The most interesting borderline case are (3,7):73≈.42>2−1, which leads to the (20,21,29) triangle, (5,13):135≈.385<2−1, which leads to the (65,72,97) triangle, and (7,17):177≈.411<2−1 which leads to the (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.