PUMaC 2020 · 数论（A 组） · 第 6 题
PUMaC 2020 — Number Theory (Division A) — Problem 6
题目详情
- Find the number of ordered pairs of integers ( x, y ) such that 2167 divides 3 x + 27 y + 2021 with 0 ≤ x, y ≤ 2166. v n
解析
- Find the number of ordered pairs of integers ( x, y ) such that 2167 divides 3 x + 27 y + 2021 with 0 ≤ x, y ≤ 2166. Proposed by: Aleksa Milojevic Answer: 2352 First, we observe that 2167 = 11 · 197 , and so by Chinese Remainder Theorem we just determine the number of ways to do this for p = 11 and p = 197 . 2 2 2 2 For p = 11 , this reduces down to the congruence 3 x +27 y ≡ 3 (mod 11) , or that x +9 y ≡ 1 2 2 (mod 11) . Since 9 is a square, we see that we can write z = 3 y and solve x + z ≡ 1 (mod 11) , and get the same number of solutions (since we can then find y again given z ). 2 2 2 2 As for p = 197 , we get that 3 x + 27 y ≡ 51 (mod 197) , or that x + 9 y ≡ 17 (mod 197) , 2 2 which we may again write as x + z ≡ 17 (mod 197) . Notice, however, that 197 ≡ 1 (mod 4) , meaning that 17 is a quadratic residue of 197 if and only if 197 is one of 17 , or that 10 is a 8 4 square (mod 17) . We can see that 10 (mod 17) ≡ ( − 2) (mod 17) ≡ − 1 (mod 17) , meaning that, in fact, 17 is a non-quadratic residue (mod 197) . We now claim that the first equation has 12 solutions, and the second has 196 . Here let p = 197 2 2 and r = 17 . Let the number of solutions be N for x + z ≡ r (mod p ) , where r 6 = 0 . Then, we ( ) ( ) ( ) ( ) ( )( ) ∑ ∑ ∑ ∑ a b a b a b have N = (1 + )(1 + ). Thus N = p + + + . The a + b = r a b a + b = r p p p p p p first two sums are easily seen to be 0 . As for the third one, we consider the possibilities that we’re allowed to have. First, suppose that a, b are both squares; notice then that, since 197 ≡ 1 2 2 (mod 4) , − 1 is a square too, so we find the number of solutions to ( x − y )( x + y ) = x − y ≡ r (mod 197) . Notice that, given x − y 6 = 0 , we can find x + y and thus x, y. This yields us with 196 solutions. But considering the signs that are allowed, we see that we can negate x, y freely, and since 17 isn’t a square modulo 196 , but − 1 is, we can’t have either be 0 , yielding us with p − 1 = 49 solutions here. 4 p +1 Therefore, since we have = 99 squares, we thus have 50 pairs where a is a square, b isn’t, 2 and so 50 where b is a square, a isn’t, and therefore 48 where neither are squares. However, notice that we have two terms, namely those with (0 , 17) and (17 , 0) that we subtract because they contribute 0 , not 1 . But then notice that we get 49 + 48 − 50 − 50 + 2 = − 1 . Therefore, we have that N = p − 1 . We now run this argument for p = 11 . Notice that we end up getting that, for a + b = 1 , since − 1 is a nonquadratic residue for 11 , we see that the number where a is a square, b isn’t 2 2 is the number of solutions x − y = 1 , where y 6 = 0 . We have in total 10 solutions for x, y, of which 2 have y = 0 , and then we divide again by 4 to get 2 solutions in total. Thus, we have 6 − 2 = 4 pairs where both are squares, 2 again with one but not the other, and 3 where both are not squares. This then evaluates to 3 . But again, here we have the pairs (0 , 1) and (1 , 0) which contribute 0 each, not 1 , so we subtract 2 . Therefore, we see that we have p + 4 − 2 − 2 + 3 − 2 = p + 1 solutions here. Our answer is thus 12 · 196 = 2352 . v n