Maths Olympiad Prep

Library / /4 of 1394

Number theory Difficulty 4.5 AIME Find the answer United States

Problem:
Compute the number of positive integers n1000n \leq 1000 such that lcm(n,9)\operatorname{lcm}(n, 9) is a perfect square. (Recall that lcm denotes the least common multiple.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Suppose n=3amn=3^{a} m, where 3m3 \nmid m. Then
lcm(n,9)=3max(a,2)m \operatorname{lcm}(n, 9)=3^{\max (a, 2)} m
In order for this to be a square, we require mm to be a square, and aa to either be even or 11. This means nn is either a square (if aa is even) or of the form 3k23 k^{2} where 3k3 \nmid k (if a=1a=1).

There are 3131 numbers of the first type, namely
12,22,32,42,,302,312 1^{2}, 2^{2}, 3^{2}, 4^{2}, \ldots, 30^{2}, 31^{2}
There are 1212 numbers of the second type, namely
312,322,342,352,,3162,3172 3 \cdot 1^{2}, 3 \cdot 2^{2}, 3 \cdot 4^{2}, 3 \cdot 5^{2}, \ldots, 3 \cdot 16^{2}, 3 \cdot 17^{2}
Overall, there are 31+12=4331+12=43 such 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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.