PUMaC 2017 · 数论（A 组） · 第 7 题
PUMaC 2017 — Number Theory (Division A) — Problem 7
题目详情
- Compute the number of ordered pairs of integers ( a, b ), where 0 ≤ a < 17 and 0 ≤ b < 17, 2 3 such that y ≡ x + ax + b (mod 17) has an even number of solutions ( x, y ), where 0 ≤ x < 17 and 0 ≤ y < 17 are integers. 100 ∑
解析
- Let p = 17. We work modulo p . Note that solutions come in pairs ( x, y ) and ( x, − y ) (i.e. ( x, p − y )), except for solutions ( x, 0). Thus, the number of solutions is even if and only if 3 x + ax + b has an even number of distinct roots modulo p . To count such pairs ( a, b ) we employ complementary counting. 2 3 If x + ax + b has three distinct roots, it can be written in the form ( x − r )( x − s )( x + r + s ) for r 6 = s , r 6 = − r − s (so s 6 = − 2 r ), and s 6 = − r − s (so r 6 = − 2 s ). The number of such pairs 2 2 ( r, s ) is p − 3 p + 2. This is because there are p pairs ( r, s ); p have r = s , p have r = − 2 s , p have s = − 2 r , and it is easy to see that there is no overlap, with the exception of (0 , 0), which 2 we counted thrice. Thus, p − 3 p + 2 pairs ( r, s ) satisfy these conditions. Now, since we can 3 permute the roots r , s , and − r − s as we wish, the number of polynomials x + ax + b with 2 p − 3 p +2 three roots is . 6 3 2 If x + ax + b has exactly one root, it can be written as ( x − r )( x + rx + c ) for some ( r, c ), where 2 x + rx + c is irreducible. Thus, the number of such polynomials is the number of irreducible 2 2 polynomials x + rx + c . The total number of quadratics modulo p is p , and the number ( ) p of reducible quadratics is p + (because a reducible quadratic either has a double root — 2 ( ) p ( p − 1) p 2 there are p of these — or has two distinct roots). This leaves p − p − = irreducible 2 2 p ( p − 1) 3 quadratics, and thus polynomials of the form x + ax + b with exactly one root. 2 2 2 p − 3 p +2 p − p Thus, there are + such polynomials with an odd number of distinct roots, and 6 2 2 since there are p polynomials total ( p possibilities for a and p possibilities for b ), the number of polynomials with an even number of distinct roots, and thus the number of pairs ( a, b ) such 2 3 that y = x + ax + b has an even number of solutions modulo p , is ( ) 2 2 2 2 p − 3 p + 2 p − p 2 p + 6 p − 2 p + 3 p − 1 2 p − + = = . 6 2 6 3 Plugging in p = 17, we obtain 113 as our answer. Problem written by Eric Neyman a +99 ∑