PUMaC 2011 · 数论（B 组） · 第 4 题

PUMaC 2011 — Number Theory (Division B) — Problem 4

[ 4 ] What is the largest positive integer n < 1000 for which there is a positive integer m satisfying lcm( m, n ) = 3 m × gcd( m, n )? p p

解析

Using the identity that lcm ( m, n ) · gcd ( m, n ) = m · n , it follows that m · n 2 3 m × gcd ( m, n ) = lcm ( m, n ) = = ⇒ n = 3[gcd ( m, n )] . gcd ( m, n ) √ It follows that n must be three times a perfect square. If we set m = n/ 3, which is an integer, it follows that √ √ √ √ √ lcm ( n/ 3 , n ) = n = 3 n/ 3 · n/ 3 = 3 n/ 3 · gcd ( n/ 3 , n ) , as desired. Hence, every triple of a perfect square works as a value of n , and the largest such 2 under 1000 is 3 · 18 = 972 . 3 6 3 2