PUMaC 2016 · 数论（A 组） · 第 8 题
PUMaC 2016 — Number Theory (Division A) — Problem 8
题目详情
- Let n = 2 · 3 · 5 · 7 . For k a positive integer, let f ( k ) be the number of integers 0 ≤ x < n 2 2 such that x ≡ k (mod n ). Compute the number of positive integers k such that k | f ( k ). 1
解析
- Fix k . We note that x ≡ k (mod n ) if and only if ( x − k )( x + k ) ≡ 0 (mod n ), i.e. ( x − k )( x + k ) 8 9 10 11 is divisible by each of 2 , 3 , 5 , and 7 . Note that by the Chinese remainder theorem, we 8 9 10 11 may characterize each 0 ≤ x < n as x modulo each of 2 , 3 , 5 , and 7 . Note also that 8 8 divisibility by 2 depends exclusively on x modulo 2 , and similarly for the other primes. Let v ( m ) denote the number of times a prime p goes into the factorization of m . We first p 8 examine divisibility modulo 2 . If v ( k ) = 0, i.e. k is odd, then x − k and x + k differ by 2 k , 2 so either both are odd (impossible) or one will be divisible by 2 and not 4, so the other one 7 8 must be divisible by 2 (this is necessary and sufficient). Thus, x modulo 2 is a multiple of 7 2 2 plus or minus k , so there are 2 possible values of x . If v ( k ) = 1 then we get a similar 2 8 result except that one of x − k and x + k must be divisible by 4 and not 8, so x modulo 2 6 3 is a multiple of 2 plus or minus k , meaning that there are 2 possible values of x . Similarly, 4 if v ( k ) = 2 then there are 2 possible values of x . But if v ( k ) = 3 then we get that one of 2 2 4 4 x − k and x + k must be divisible by 2 , but then the other is also divisible by 2 . This means 4 3 that x is any number that is off from a multiple of 2 by an odd multiple of 2 , i.e. x is any 3 4 4 number divisible by 2 and not 2 ; there are 2 of these. If v ( k ) is 4 or larger then clearly 2 8 4 4 ( x − k )( x + k ) is divisible by 2 if and only if x is a multiple of 2 , so there are again 2 values of x . Thus we get the following chart. 2 8 v ( k ) # values of x modulo 2 2 2 0 2 3 1 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 2 4 7 2 4 8 2 . . . . . . r r Now we examine divisibility modulo p for p 6 = 2. If v ( k ) < then one of x − k and x + k p 2 r − v ( k ) p must be divisible by p , and this is a sufficient condition (because then the other will be v ( k ) v ( k ) r p p divisible by p ), so there are 2 · p possible values of x . If v ( k ) ≥ then one of x − k p 2 r d e 2 and x + k must be divisible by p , and therefore so must x (and this is sufficient), so there r b c 2 are p possible values of x . Thus we get the following chart, where each entry represents (as r above) the number of x -values modulo p , where p goes into n r times. v ( k ) p = 3 p = 5 p = 7 p 0 2 2 2 1 2 · 3 2 · 5 2 · 7 2 2 2 2 2 · 3 2 · 5 2 · 7 3 3 3 3 2 · 3 2 · 5 2 · 7 4 4 4 4 2 · 3 2 · 5 2 · 7 4 5 5 5 3 5 2 · 7 4 5 5 6 3 5 7 4 5 5 7 3 5 7 . . . . . . . . . . . . Note that for p > 7, we must have v ( k ) = 0 because f ( k ) cannot divide a prime that does not p go into n . Also, f ( k ) is the product for each prime p of the number of possible x -values for p , as determined b v ( k ). We notice that v ( k ) ≤ 4, v ( k ) ≤ 5, and v ( k ) ≤ 5, because otherwise p 3 5 7 k contains a larger power of the prime than the number of possible x -values (and thus f ( x )). We consider two cases. Suppose that v ( k ) < 5. Then f ( k ) has three 2’s in its prime factorization coming from the 5 number of x -values for p = 3, 5, and 7, so from our first chart we see that v ( k ) can be any 2 number less than or equal to 7. Thus, the number of possible values of k here, which is the number of possible pairs ( v ( k ) , v ( k ) , v ( k ) , v ( k )), is 8 · 5 · 5 · 6. 2 3 5 7 Now suppose that v ( k ) = 5. Then f ( k ) has two 2’s in its prime factorization coming from the 5 number of x -values for p = 3, 5, and 7 (5 does not contribute a 2), so v ( k ) can be any number 2 less than or equal to 6. Thus, in this case the number of possible values of k is 7 · 5 · 1 · 6. Thus, our answer is 5 · 6(8 · 5 + 7) = 47 · 30 = 1410 . Problem written by Heesu Hwang and Eric Neyman. If you believe that any of these answers is incorrect, or that a problem had multiple reason- able interpretations or was incorrectly stated, you may appeal at tinyurl.com/pumacappeals . All appeals must be in by 1 PM to be considered. 3