HMMT 二月 2012 · 冲刺赛 · 第 21 题

HMMT February 2012 — Guts Round — Problem 21

[ 13 ] Let N be a three-digit integer such that the difference between any two positive integer factors of N is divisible by 3. Let d ( N ) denote the number of positive integers which divide N . Find the maximum possible value of N · d ( N ).

解析

[ 13 ] Let N be a three-digit integer such that the difference between any two positive integer factors of N is divisible by 3. Let d ( N ) denote the number of positive integers which divide N . Find the maximum possible value of N · d ( N ). Answer: 5586 We first note that all the prime factors of n must be 1 modulo 3 (and thus 1 modulo 4 6). The smallest primes with this property are 7 , 13 , 19 , . . . . Since 7 = 2401 > 1000, the number can have at most 3 prime factors (including repeats). Since 7 · 13 · 19 = 1729 > 1000, the most factors N can 2 have is 6. Consider the number 7 · 19 = 931, which has 6 factors. For this choice of N , N · d ( N ) = 5586. For another N to do better, it must have at least 6 factors, for otherwise, N · d ( N ) < 1000 · 5 = 5000. 2 It is easy to verify that 7 · 19 is the greatest number with 6 prime factors satisfying our conditions, so the answer must be 5586.