HMMT 二月 2015 · 团队赛 · 第 9 题

英文解析

9. [ 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, andk (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-coefficientj kpolynomial symmetric in the ω (for the r residues j (mod r )), and also symmetric in the z (for thep residues k (mod p )). So by the fundamental theorem of symmetric sums, it can be written as aninteger-coefficient polynomial in the symmetric sums of the ω together with the symmetric sums of thejkz . 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,bwhere 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 apr 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 asr
   Fermat’s little theorem on ( − 2) − 1.
   Finally, we plug in the specific numbers:
   101 · 10 10
   ( − 1) [( − 2) − 1] = 1023 ≡ 13 (mod 101) .
   α − β
   Here we are using congruence of algebraic integers modulo p , so that α ≡ β (mod p ) if and only if is an algebraic 6
   u − v u − vpinteger. 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 isodd, etc.).
   Solution 2 (sketch). Here we sketch a better solution found by several teams, but missed by theauthor (primarily due to blindness from having first found the first solution). The proof of the firstpart (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 cthat D := ( ω + z + z ) − ( ω + 1 + 1 ) is an algebraic integer divisible by z − 1. But Da,b,c a,b,cis also a difference of integers, hence an integer itself. The only way can be an algebraic integer is dz − 1
   ∏
   a b cif p | D (Why?), so it simply remains to compute the remainder when the integer ( ω + 1 + 1 )
   a,b,cis 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 rprevious solution), so (up to sign) we want to evaluate (1 + ( z + z ) ) (mod p ). But we haveb,c
   ∏
   b c ra polynomial identity (1 + ( T + T ) ) ∈ Φ ( T ) · Z [ x ] + M for some constant integer M , whereb,cpp − 1
   Φ ( T ) = T + · · · + T + 1 denotes the p th cyclotomic polynomial. But note that Φ ( z ) = 0 isp pcongruent to Φ (1) = p modulo p , sop
   ∏ ∏
   b c r b c r
   (1 + ( z + z ) ) − (1 + (1 + 1 ) )
   b,c b,cis an integer divisible by p . The rest is easy.
   ∏
   Remark. Without using the Frobenius map, this second solution gives another proof that ( ω +ab b r
   1 mz + · · · + 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 stepof the second solution)?
   Remark. The central idea behind the second solution is that if f ( z ) is an integer for some polynomialf ∈ Z [ x ], then it’s congruent to (the integer) f (1) modulo p . Can you generalize this, say when z isnot necessarily a root of unity?
   ∞ ∞