HMMT 二月 2015 · 团队赛 · 第 9 题
HMMT February 2015 — Team Round — Problem 9
题目详情
- [ 40 ] Let z = e and let ω = e . Prove that 9 100 100 ∏ ∏ ∏ a b c ( ω + z + z ) a =0 b =0 c =0 is an integer and find (with proof) its remainder upon division by 101. ∞ ∞
解析
- [ 40 ] Let z = e and let ω = e . Prove that 9 100 100 ∏ ∏ ∏ a b c ( ω + z + z ) a =0 c =0 b =0 is an integer and find (with proof) its remainder upon division by 101. Answer: 13 Solution 1. Let p = 101 and r = 10. Note that p ∤ r . ∏ k p In the sequel, we will repeatedly use the polynomial identities ( x − z ) = x − 1, and k (mod p ) ∏ j r ( x − ω ) = x − 1. j (mod r ) The product is an integer by standard symmetric sum theory (concrete precursor to Galois theory, though one doesn’t need the full language). More precisely, it expands into an integer-coefficient j k polynomial symmetric in the ω (for the r residues j (mod r )), and also symmetric in the z (for the p residues k (mod p )). So by the fundamental theorem of symmetric sums, it can be written as an j integer-coefficient polynomial in the symmetric sums of the ω together with the symmetric sums of the k z . But these symmetric sums are integers themselves, so the original expression is indeed an integer. 6 p p p To actually compute the remainder modulo p , note by the Frobenius endomorphism ( u + v ) ≡ u + v (mod p ) that ∏ ∏ a b c p a b p ( ω + z + z ) = ( − 1) (( − ω − z ) − 1) a,b,c a,b ∏ ∏ pa pb p pa ≡ ( ω + z − ( − 1) ) = ( ω + 2) (mod p ) , a,b a,b where we use p ≡ 1 (mod 2) in the last step. This simplifies further to ∏ ∏ p pa p p a p ( − 1) ( − 2 − ω ) = ( − 1) ( − 2 − ω ) a a pr r p pr r = ( − 1) [( − 2) − 1] ≡ ( − 1) [( − 2) − 1] (mod p ) , where we’ve used the fact that { pa (mod r ) } = { a (mod r ) } (since p is invertible mod r ), as well as r Fermat’s little theorem on ( − 2) − 1. Finally, we plug in the specific numbers: 101 · 10 10 ( − 1) [( − 2) − 1] = 1023 ≡ 13 (mod 101) . α − β 6 Here we are using congruence of algebraic integers modulo p , so that α ≡ β (mod p ) if and only if is an algebraic p u − v u − v integer. In particular, for integers u, v , is an algebraic integer if and only if is an integer. p p Team Remark. By repeatedly getting rid of “ z ” terms and applying the Frobenius map, one can show that ∏ a b b r 1 m ( ω + z + · · · + z ) is an integer congruent to something like m + 1 modulo p (as long as p is odd, etc.). Solution 2 (sketch). Here we sketch a better solution found by several teams, but missed by the author (primarily due to blindness from having first found the first solution). The proof of the first part (that the product is an integer) is the same, so we only sketch different proofs of the second part (computation of the remainder mod p ). For example, we can use the algebraic integer formulation from the previous solution. Indeed, note ∏ ∏ a b c a b c that D := ( ω + z + z ) − ( ω + 1 + 1 ) is an algebraic integer divisible by z − 1. But D a,b,c a,b,c D is also a difference of integers, hence an integer itself. The only way can be an algebraic integer is z − 1 ∏ a b c if p | D (Why?), so it simply remains to compute the remainder when the integer ( ω + 1 + 1 ) a,b,c is divided by p , which is quite easy. Alternatively (as some contestants/teams found), we can get rid of ω first (rather than z as in the ∏ b c r previous solution), so (up to sign) we want to evaluate (1 + ( z + z ) ) (mod p ). But we have b,c ∏ b c r a polynomial identity (1 + ( T + T ) ) ∈ Φ ( T ) · Z [ x ] + M for some constant integer M , where p b,c p − 1 Φ ( T ) = T + · · · + T + 1 denotes the p th cyclotomic polynomial. But note that Φ ( z ) = 0 is p p congruent to Φ (1) = p modulo p , so p ∏ ∏ b c r b c r (1 + ( z + z ) ) − (1 + (1 + 1 ) ) b,c b,c is an integer divisible by p . The rest is easy. ∏ a Remark. Without using the Frobenius map, this second solution gives another proof that ( ω + b b r 1 m z + · · · + z ) is an integer congruent to something like m + 1 modulo p (as long as p is odd, etc.). Can you reconcile this difference (e.g. is the use of Frobenius in the first solution equivalent to a step of the second solution)? Remark. The central idea behind the second solution is that if f ( z ) is an integer for some polynomial f ∈ Z [ x ], then it’s congruent to (the integer) f (1) modulo p . Can you generalize this, say when z is not necessarily a root of unity? ∞ ∞