PUMaC 2022 · 团队赛 · 第 5 题
PUMaC 2022 — Team Round — Problem 5
题目详情
- You’re given the complex number ω = e + e + e + e , and told it’s a 3 2 root of a unique monic cubic x + ax + bx + c, where a, b, c are integers. Determine the value 2 2 2 of a + b + c .
解析
- You’re given the complex number ω = e + e + e + e , and told it’s a 3 2 root of a unique monic cubic x + ax + bx + c, where a, b, c are integers. Determine the value 2 2 2 of a + b + c . Proposed by Frank Lu Answer: 18 Observe first that the exponents of ω are precisely those of the form 2 πir/ 13 , where r is a 3 cubic residue (mod 13) . Indeed, notice that the values of r we have are r = 1 , 5 ≡ − 8 = ( − 2) 12 P 3 3 2 πij/ 13 (mod 13) , 8 = 2 , and − 1 = ( − 1) . Given as well the identity that e = − 1 , this j =1 suggests that the other two roots of this cubic are going to be the following complex numbers: 4 iπ/ 13 20 iπ/ 13 32 iπ/ 13 48 iπ/ 13 ω = e + e + e + e , 1 8 iπ/ 13 40 iπ/ 13 64 iπ/ 13 96 iπ/ 13 ω = e + e + e + e , 2 which were obtained from ω by multiplying the cubic residues by two and four. These 12 exponents, along with 0 , are 2 πi/ 13 times a complete residue class (mod 13) . (This can actually be proven with Galois theory, but this is not important for the solution itself). We now try finding the coefficients by computing ω + ω + ω, ω ω + ω ω + ω ω , ωω ω , which 1 2 1 2 1 2 1 2 are obtained by Vieta’s formulas. The first, as we mentioned before, is − 1 . For the other two, we analyze these terms by substituting the sums in and expanding out the products. For the second product, for instance, notice that we get 3 · 4 · 4 = 48 terms. We 2 πir/ 13 now consider the number of these terms that are equal to e for each residue r. Notice that this is equal to the number of cubic residues s, t so that s + 2 t ≡ r (mod 13) plus the number of cubic residues s, t so that s + 4 t ≡ r (mod 13) plus the number where 2 s + 4 t ≡ r 2 πir/ 13 (mod 13) . Each of these are obtained just from considering what it means for a term e to be obtained from one of the products. However, we claim that we can biject these solutions together. To see this, we can combine j j +1 these equations into the form s 2 + t 2 = r, where s, t are cubic residues and j ∈ { 0 , 1 , 2 } . It’s ′ ′ not hard to see then that ( s, t, j ) is a solution for r = 1 if and only if ( r s, r t, j ) is a solution ′ ′ if r is a nonzero cubic residue, and that this is a bijection between solutions. If r is twice a ′ ′ cubic residue, notice that ( s, t, j ) is a solution for r = 1 if and only if ( r s/ 2 , r t/ 2 , j + 1) is a ′ ′ solution if j = 0 , 1 , and (4 r s, 4 r t, 0) if j = 2 . A similar procedure works for four times a cubic 2 πir/ 13 residue. This means that the number of times that e appears for each nonzero residue r is the same. And as there are four solutions for r = 1 , namely 1 = ( − 1) + 2 ∗ (1) , 2 ∗ (5) + 4 ∗ (1) , 4 ∗ (8) + 8 ∗ 1 , 4 ∗ ( − 1) + 8 ∗ ( − 1) , it follows there are 4 copies of each residue, which means that this pairwise product equals − 4 . Finally, we consider ωω ω . Notice that again, the number of terms with residue r is the 1 2 number of solutions to r = s + 2 t + 4 u, where s, t, u are cubic residues. Here, we see again that all nonzero r have the same number of solutions. We just need to find the number of solutions to s + 2 t + 4 u ≡ 0 (mod 13) . Notice that by scaling up s we may assume that s = 1; from here notice that by going through the values for t the only solution we have are (1 , 8 , 12) . This 64 − 4 means there are 4 solutions for r = 0 and = 5 for all nonzero residues. 12 Therefore, we see that the value of this product is equal to 4 − 5 , as the sum of this exponential 3 2 for nonzero residues is equal to − 1 . Our polynomial is thus x + x − 4 x + 1 , and so our answer is 1 + 16 + 1 = 18 . 3