PUMaC 2020 · 数论（A 组） · 第 7 题
PUMaC 2020 — Number Theory (Division A) — Problem 7
题目详情
- Let φ ( x, v ) be the smallest positive integer n so that 2 divides x + 95 if it exists, or 0 if no ∑ 255 such positive integer exists. Determine φ ( i, 8). i =0
解析
- Let φ ( x, v ) be the smallest positive integer n so that 2 divides x + 95 if it exists, or 0 if no ∑ 255 such positive integer exists. Determine φ ( i, 8). i =0 Proposed by: Frank Lu Answer: 2704 All equivalences here are mod 256. 8 First, we observe that 6561 + 95 ≡ 6656 = 256 ∗ 26 ≡ 0, and 6561 = 3 , so we can write the 8 n 8 desired divisibility as 2 | x − 3 . 3 a We now instead compute the number of i such that φ ( i, 8) = n for each n > 0. Write n = b 2 , where b is odd. First, we’ll show that a ≤ 3 for there to be at least one solution. 2 2 2 By continuing squaring, we see that ( − 95) ≡ 65 , 65 ≡ 129 , 129 ≡ 1, which means that 64 32 64 3 ≡ 1, but 3 is not equivalent to 1. But note that x − 1 ≡ 0 for all odd x , since writing a 64 2 b 2 8 x = 2 y + 1 yields that x − 1 ≡ 128( y + 63 y ) ≡ 0. Thus, x ≡ 3 , with a > 3, implies that 9 − a 2 1 ≡ 3 , contradiction with a > 3. b Now, we know that a ≤ 3. Note that we expand out to get that we want x so that ( x − 3 − a 3 − a a − 1 2 2 b 2 2 b 2 3 )( x + 3 ) . . . ( x + 3 ). Note that none of the terms other than the first 2 can contribute a power of 2 that is larger than 2, since these terms will be equivalent to 2 mod 4. Note also that at most one of the first two terms can be divisible by 4. 3 − a 3 − a b 2 8 − a b 2 8 − a If a > 0, then either x ≡ 3 mod 2 , or x ≡ − 3 mod 2 . If a = 0, this is just b 8 x ≡ 3 . But b is odd, so it has an inverse modulo any power of 2. Raising each of these equations to 8 − a their appropriate powers yields a unique solution modulo 2 . a +1 Thus, the number of solutions for n is 1 if a = 0 and 2 if 1 ≤ a ≤ 3. m n 8 a b Now, say x ≡ x ≡ 3 . Write m = y 2 , n = z 2 , with y, z odd. If a 6 = b , WLOG a < b . a b − a b − a 2 (2 y − z ) b − a Then x = 1 gives that x ≡ 1. But 2 y − z would be odd, so we can raise a a b − a 2 y 2 8 this to 2 y − z ’s inverse modulo 64, giving x ≡ 1, which means that x = 3 ≡ 1, a contradiction. a 2 ( y − z ) 8( y − z ) If a = b , repeating this yields that x ≡ 1, or that 3 , by raising to the y th power. But then we note that y − z must be divisible by 8. Thus, we see that we have 16 possible values of n : 1 , 3 , 5 , 7 , 2 , 6 , 10 , 14 , 4 , 12 , 20 , 28 , 8 , 24 , 40 , 56. Summing these yields the answer (1+3+5+7)(1 ∗ 1+2 ∗ 4+4 ∗ 8+8 ∗ 16) = 16 ∗ (1+8+32+128) = 16 ∗ (169) = 2704.