Maths Olympiad Prep

Library / /116 of 860

Number theory Difficulty 4.8 AIME Find the answer

Compute the number of positive integers n1000n \leq 1000 such that \operatorname{lcm}(n, 9)$ is a perfect square.

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

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 1 . 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 31 numbers of the first type, namely 12,22,32,42,,302,3121^{2}, 2^{2}, 3^{2}, 4^{2}, \ldots, 30^{2}, 31^{2} There are 12 numbers of the second type, namely 312,322,342,352,,3162,31723 \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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.