PUMaC 2021 · 团队赛 · 第 12 题
PUMaC 2021 — Team Round — Problem 12
题目详情
- Given an integer a , we define a sequence of real numbers a , a , . . . using the relation 0 0 1 2 2 a = 1 + ia , i i − 1 for i ≥ 1. An index j is called good if a can be an integer for some a . Determine the sum of j 0 the indices j which lie in the interval [0 , 99] and which are not good. k P e e e 1 2 k
解析
- Given an integer a , we define a sequence of real numbers a , a , . . . using the relation 0 0 1 2 2 a = 1 + ia , i i − 1 for i ≥ 1. An index j is called good if a can be an integer for some a . Determine the sum of j 0 the indices j which lie in the interval [0 , 99] and which are not good. Proposed by: Frank Lu Answer: 4946 We claim that the only ones that are possible, where a can be an integer, are j = 0 , 1 , 3 . To j k P k 2 2 see this, we first claim that, given a , we have that a = j ! + k ! a , where k ≥ 1 . To 0 0 k j j =0 prove this, we use induction: for j = 1 , this is given by the formula. From here, we notice k +1 P k +1 2 2 2 that for a , this is equal to 1 + ( k + 1) a = 1 + ( j + 1)! + ( k + 1)! a , which gives us 0 k +1 k j +1 j =1 2 2 our desired. It’s also not too hard to check that a = 3 + 2 a cannot be a perfect square, by 2 0 considering this equation (mod 9) . 5 2 2 Now notice that if k ≥ 3 , taking the terms modulo 3 yields us with a ≡ 1 + k (mod 3) , k which is only a quadratic residue when k is divisible by 3 . By a similar logic, notice that this is 2 equivalent to 5 (mod k − 2); for a to be a perfect square, we need 5 to be a quadratic residue k modulo k − 2 . However, we know that, by quadratic reciprocity, we know that for each prime p dividing k − 2 , since 5 ≡ 1 (mod 4) , we have that this is a valid quadratic residue if and only if every odd prime p dividing k − 2 is a quadratic residue (mod 5) , which in turn holds if and only if every odd prime dividing k − 2 is either 1 or 4 (mod 5) . Therefore, listing the odd primes that are 1 , 4 (mod 5) , we note that these are 11 , 19 , 29 , 31 , 41 , 59 , 61 , 71 , 79 , 89 (or k − 2 = 1 . ) Therefore, the possible values of k − 2 are these values, with some additional powers of 2 , so k − 2 can be either a power of 2 , or one of 11 , 22 , 44 , 88 , 19 , 38 , 76 , 29 , 58 , 31 , 62 , 41 , 82 , 59 , 61 , 71 , 79 , 89 . However, k − 2 cannot be divisible by 8 , since 5 is not a quadratic residue modulo 8 . So this narrows our values down to 1 , 2 , 4 , 11 , 22 , 44 , 19 , 38 , 76 , 29 , 58 , 31 , 62 , 41 , 82 , 59 , 61 , 71 , 79 , 89 for k − 2 , or that k is one of 3 , 4 , 6 , 13 , 24 , 46 , 21 , 40 , 78 , 31 , 60 , 33 , 64 , 43 , 84 , 61 , 63 , 73 , 81 , 91 . From here, we can also check this (mod 8) , by considering the terms j = 0 , 1 , 2 , 3; we get 2 2 that a ≡ 1 + k + k ( k − 1) + k ( k − 1)( k − 2) = k (( k − 1) + 1) + 1 (mod 8) . This has to be k equivalent to either 0 , 1 , or 4 (mod 8) . Taking a look at the terms, we thus see that k has to either be divisible by 4 , or it has to be equivalent to 3 (mod 4) . So k is narrowed down to 3 , 4 , 24 , 40 , 31 , 60 , 64 , 43 , 84 , 63 , 91 . Next, taking this modulo k − 1 yields that 2 must be a quadratic residue (mod k − 1) , which means that the only odd primes dividing k − 1 are 1 , 7 (mod 8) . Checking through our list, we rule our 4 , 40 , 31 , 60 , 64 , 43 , 84 , 91 , so we are left with just 3 , 24 , 63 . Finally, we want to rule out 24 and 63 . For these values, observe that modulo k − 4 we have 2 a ≡ 1 + 4 + 12 + 24 + 24 ≡ 65 (mod k − 4) for k ≥ 5 . But for k = 63 , this implies that 6 is k a square modulo 59 . But 2 isn’t a square modulo 59 as 59 ≡ 3 (mod 8) , but 3 is since 59 ≡ 2 (mod 3) , and 59 ≡ 3 (mod 4) and employing quadratic reciprocity. 2 Similarly, modulo k − 5 yields that a ≡ 1 + 5 + 20 + 60 + 120 + 120 ≡ 326 (mod k − 5) , which k for k = 24 yields us with 3 (mod 19) . But by quadratic reciprocity, since 19 ≡ 3 (mod 4) and 19 ≡ 1 (mod 3) (so is a square modulo 3), 3 isn’t a square modulo 19 , so k = 24 is also impossible. 2 2 Finally, notice that a = 10 + 6 a , which is clearly a perfect square when a = 1 . We thus see 0 3 0 99 · 100 that 0 , 1 , 3 are the only ones that work, yielding our sum of − 4 = 4946 . 2 k P e e e 1 2 k