Maths Olympiad Prep

Library / /55 of 82

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:

For a positive integer nn, let p(n)p(n) denote the product of the positive integer factors of nn. Determine the number of factors nn of 23102310 for which p(n)p(n) is a perfect square.

Solution

Solution:

Answer: 2727

Note that 2310=2×3×5×7×112310 = 2 \times 3 \times 5 \times 7 \times 11. In general, we see that if nn has d(n)d(n) positive integer factors, then p(n)=nd2p(n) = n^{\frac{d}{2}} since we can pair factors (d,nd)(d, \frac{n}{d}) which multiply to nn. As a result, p(n)p(n) is a square if and only if nn is a square or dd is a multiple of 44.

Thus, because 23102310 is not divisible by the square of any prime, we claim that for integers nn dividing 23102310, p(n)p(n) is even if and only if nn is not prime. Clearly, p(n)p(n) is simply equal to nn when nn is prime, and p(1)=1p(1) = 1, so it suffices to check the case when nn is composite. Suppose that n=p1p2pkn = p_1 p_2 \cdots p_k, where k>1k > 1 and {p1,,pk}\{p_1, \ldots, p_k\} is some subset of {2,3,5,7,11}\{2, 3, 5, 7, 11\}. Then, we see that nn has 2k2^k factors, and that 42k4 \mid 2^k, so p(n)p(n) is a square.

Since 23102310 has 25=322^5 = 32 factors, five of which are prime, 2727 of them have p(n)p(n) even.

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.