PUMaC 2015 · 数论（A 组） · 第 6 题
PUMaC 2015 — Number Theory (Division A) — Problem 6
题目详情
- [ 6 ] For a positive integer n , let d ( n ) be the number of positive divisors of n . What is the smallest positive integer n such that ∑ 3 d ( t ) t | n is divisible by 35?
解析
- [ 6 ] For a positive integer n , let d ( n ) be the number of positive divisors of n . What is the smallest positive integer n such that ∑ 3 d ( t ) t | n is divisible by 35? Solution: ∏ k e i First, one can check that if n = p is its prime factorization (with each p distinct and i i =1 i ∏ k 3 3 3 1 ≤ e ≤ k ), then d ( n ) = ( e + 1). So, we see that gcd ( a, b ) = 1 = ⇒ d ( ab ) = d ( a ) d ( b ) . i i i =1 ∏ k f i This implies that if t = p where 0 ≤ f ≤ e , i i i i =1 k k k e i ∑ ∑ ∏ ∏ ∑ ∏ ∑ f 3 3 3 3 i d ( t ) = d ( p ) = d ( s ) = ( j + 1) . i f i =1 i =1 i =1 j =0 t | n t | n i s | p i Above, we used the fact that as t ranges over the divisors of n , the exponents f each range i ∑ ∑ n n 3 2 from 0 to e . Therefore, using the well-known identity that i = ( i ) , the above i i =0 i =0 becomes 2 ( ) e k k i 2 ∏ ∑ ∏ ( c + 1)( c + 2) i i ( j + 1) = . 2 i =1 j =0 i =1 2 For this expression to be divisible by 35, we need ( c + 1)( c + 2) to be divisible by 5 for some i i i and by 7 for some i . If these are two different values of i , the smallest possible values are 3 and 5, respectively. Setting c = 3, c = 5, p = 3, and p = 2 gives the smallest possible 1 2 1 2 5 3 value of n in this case, which is 2 · 3 = 864. If the two values of i are the same, then the smallest possible value of c such that ( c + 1)( c + 2) is divisible by both 5 and 7 is if c = 13. i i i i 13 Setting p = 2, this yields n = 2 > 864. Thus, the answer is 864 . Authors: Steven Kwon, Eric Neyman