PUMaC 2020 · 数论（B 组） · 第 7 题
PUMaC 2020 — Number Theory (Division B) — Problem 7
题目详情
- We say that a positive integer n is divable if there exist positive integers 1 < a < b < n ∑ k 1 i such that, if the base- a representation of n is a a , and the base- b representation of n is i i =0 ∑ ∑ ∑ k k k 2 2 1 i i i b b , then for all positive integers c > b , we have that b c divides a c . Find i i i i =0 i =0 i =0 the number of non-divable n such that 1 ≤ n ≤ 100. 2 2
解析
- We say that a positive integer n is divable if there exist positive integers 1 < a < b < n ∑ k 1 i a a , and the base- b representation of n is such that, if the base- a representation of n is i i =0 ∑ ∑ ∑ k k k 2 2 1 i i i b b , then for all positive integers c > b , we have that b c divides a c . Find i i i i =0 i =0 i =0 the number of non-divable n such that 1 ≤ n ≤ 100. Proposed by: Frank Lu Answer: 27 First, note that if n can be written as pq , where 1 < p < q are positive integers, then note that the base n − 1 representation of n is 1( n − 1) + 1, and the base q − 1 representation p ( q − 1) + p , and for c > n − 1 we have that (( c − 1) + 1) | ( p ( c − 1) + c ). Thus, we only need to consider the positive integers that aren’t primes or square of primes. 2 2 Also, for p > 2, we see that base p − 1 yields that p gives ( p − 1) + 2( p − 1) + 1, and base 2 2 2 2 p − 1 yields p − 1 + 1, so thus for c ≥ p − 1 we have that ( c + 1) | ( c + 2 c + 1) . ∑ k i Now, given integer n and base- a , suppose that the base- a representation of n is a a , let i i =0 ∑ k i p ( x ) be the polynomial a x . Then, note that if we write p ( x ) as p ( x ) q ( x ) + r ( x ), a,n i a,n b,n i =0 where r ( x ) has degree less than p ( x ). But then note that for sufficiently large x , p ( x ) > b,n b,n r ( x ). But then, we see that if r ( x ) 6 = 0, then we see that for each integer x > n that p ( x ) | r ( x ) b,n implies that r ( x ) = 0 for all x sufficiently large. But then r is the zero polynomial, giving that p ( x ) | p ( x ). b,n a,n If p ( x ) and p ( x ) are the same degree, we see that the latter is a scalar multiple of the b,n a,n former, by say, c . But then we see that c < p and we need c | p , contradiction. d Otherwise, note then that if the degree of p ( x ) is d, note then 1 < p ( a ) < a ≤ p ( a ) = n , a,n b,n a,n which means that n isn’t prime, contradiction. Thus, we see that the only non-divable numbers are primes, 4 , and 1. For 4, we see the base representations 100 and 11 , which is not possible. 2 3 We thus list out the numbers: 1 , 2 , 3 , 4 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , yielding our answer of 27. 2 2