HMMT 二月 2023 · ALGNT 赛 · 第 2 题

HMMT February 2023 — ALGNT Round — Problem 2

Compute the number of positive integers n ≤ 1000 such that lcm( n, 9) is a perfect square. (Recall that lcm denotes the least common multiple.) 4 2 2 13 4

解析

Compute the number of positive integers n ≤ 1000 such that lcm( n, 9) is a perfect square. (Recall that lcm denotes the least common multiple.) Proposed by: Luke Robitaille Answer: 43 a Solution: Suppose n = 3 m , where 3 - m . Then max( a, 2) lcm( n, 9) = 3 m. In order for this to be a square, we require m to be a square, and a to either be even or 1. This means 2 n is either a square (if a is even) or of the form 3 k where 3 - k (if a = 1). There are 31 numbers of the first type, namely 2 2 2 2 2 2 1 , 2 , 3 , 4 , . . . , 30 , 31 . There are 12 numbers of the second type, namely 2 2 2 2 2 2 3 · 1 , 3 · 2 , 3 · 4 , 3 · 5 , . . . , 3 · 16 , 3 · 17 . Overall, there are 31 + 12 = 43 such n . 4 13 2 2 4