PUMaC 2016 · 数论（A 组） · 第 5 题

PUMaC 2016 — Number Theory (Division A) — Problem 5

Let k = 2 · 3 · 5 · 7 · 53. Let S be the sum of over all ordered pairs of positive lcm( m,n ) r integers ( m, n ) where mn = k . If S can be written in simplest form as , compute r + s . s 239

解析

We have 2 2 2 gcd( m, n ) gcd ( m, n ) gcd ( m, n ) gcd ( m, n ) = = = . lcm( m, n ) lcm( m, n ) · gcd( m, n ) mn k For each prime that goes into k , we can look at the minimum of the number of times it appears in m and the number of times that it appears in n . Summing over all factors m of k gives us 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 (1 + 2 + 4 + 8 + 4 + 2 + 1 )(1 + 3 + 9 + 9 + 3 + 1 )(1 + 5 + 1 )(1 + 7 + 7 + 1 )(1 + 1) 6 5 2 3 2 · 3 · 5 · 7 · 53 where for instance picking the fifth summand from the first group, the second summand from 4 0 1 0 0 the third group, and the first summand from all other groups represents m = 2 · 3 · 5 · 7 · 53 . (Each summand represents the minimum of the number of times the relevant prime appears in m and in n .) The above expression is equal to 5 3 2 106 · 182 · 27 · 100 · 2 2 · 3 · 5 · 7 · 13 · 53 13 13 = = = , 6 5 2 3 6 5 2 3 2 2 2 · 3 · 5 · 7 · 53 2 · 3 · 5 · 7 · 53 2 · 3 · 7 882 1 so r + s = 895 . Problem written by Eric Neyman. 239 238 237