Maths Olympiad Prep

Library / /154 of 168

Number theory Difficulty 2.6 Junior Find the answer

Suppose that pp and qq are two different prime numbers and that n=p2q2n=p^{2} q^{2}. What is the number of possible values of nn with n<1000n<1000?

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

Solution

We note that n=p2q2=(pq)2n=p^{2} q^{2}=(p q)^{2}. Since n<1000n<1000, then (pq)2<1000(p q)^{2}<1000 and so pq<100031.6p q<\sqrt{1000} \approx 31.6. Finding the number of possible values of nn is thus equivalent to finding the number of positive integers mm with 1m31<10001 \leq m \leq 31<\sqrt{1000} that are the product of two prime numbers. The prime numbers that are at most 31 are 2,3,5,7,11,13,17,19,23,29,312,3,5,7,11,13,17,19,23,29,31. The distinct products of pairs of these that are at most 31 are: 2×3=6,2×5=10,2×7=14,2×11=22,2×13=26,3×5=15,3×7=212 \times 3=6, 2 \times 5=10, 2 \times 7=14, 2 \times 11=22, 2 \times 13=26, 3 \times 5=15, 3 \times 7=21. Any other product either duplicates one that we have counted already, or is larger than 31. Therefore, there are 7 such values of nn.

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.