HMMT 二月 2024 · 团队赛 · 第 10 题
HMMT February 2024 — Team Round — Problem 10
题目详情
- [60] Across all polynomials P such that P ( n ) is an integer for all integers n , determine, with proof, all 2 possible values of P ( i ) , where i = − 1 .
解析
- [60] Across all polynomials P such that P ( n ) is an integer for all integers n , determine, with proof, all 2 possible values of P ( i ) , where i = − 1 . Proposed by: Pitchayut Saengrungkongka Answer: a + bi works if and only if a, b ∈ Q and ν ( a ) , ν ( b ) ≥ 0 for all p ≡ 1 (mod 4) . p p Solution: We claim the answer is every complex number a + bi where a and b are rationals whose simplified denominators are not multiples of any prime congruent to 1 modulo 4 . The proof consists of two main steps: proving that powers of p ≡ 1 mod 4 can’t appear in the denominator, and showing all possible values are attainable. We show three different methods of the former part. Impossibility via elementary number theory We first show that no other values are possible. Indeed, it is well known that any polynomial that ( ) ∑ m n maps Z into itself must be of the form P ( n ) = a for integers a and where we treat the k k k =0 k binomials as formal polynomials. This may be proved via finite differences. ( ) i a + bi It is therefore sufficient to show that for any k , can be simplified to a fraction of the form , k c where a, b, c are integers and c is not divisible by any prime that is 1 modulo 4 . We have that ( ) i i · ( i − 1) · . . . · ( i − ( k − 1)) = . k k · ( k − 1) · . . . · 1 Pick any prime p that is 1 modulo 4 . Since p is 1 modulo 4 , there exist distinct residue classes x, y 2 2 modulo p so that x ≡ y ≡ − 1 mod p . We will show that for every integer, r ≤ k divisible by p in the denominator, we can pair it with a disjoint set, { r , r } , of two positive integers less than k in these x y two residue classes so that ( i − r )( i − r ) has real and complex parts divisible by the highest power x y of p dividing r . Thus any factor of p that is 1 modulo 4 in the denominator, exists in the numerator as well, which suffices. Start with u = 1 and repeat the following process for increasing u until there is nothing left to do. u ′ ′ u For every positive integer j ≤ k such that p | j , there exist unique j , j ∈ [ j − p , j ) satisfying x y 2 2 ′ ′ u ′ ′ ′ ′ j ≡ x mod p , j ≡ y mod p and p | j + 1 , j + 1 . So pair j with the set { j , j } , and pair its old x y x y x y ′ ′ partners if any to the old partners of j and j . x y min( u,v ( r )) p The important feature of this assignment process is that we always have at step u , p | r + x 1 2 2 2 2 2 r , r + 1 , r + 1 . Thus at the end of the process, ( i − r )( i − r ) = (( r + r ) − ( r + 1) − ( r + 1)) − y x y x y x y x y 2 v ( r ) p ( r + r ) i has real and complex parts divisible by p as claimed. x y Impossibility via Gaussian Integers We work in the ring of Gaussian Integers Z [ i ] = { a + bi : a, b ∈ Z } , which is sitting inside number field Q [ i ] = { a + bi : a, b ∈ Q } . It’s well-known that Z [ i ] is a unique factorization domain. For any Gaussian prime π , let ν ( z ) denote the exponent of π in the factorization of z . pi Let p ≡ 1 (mod 4) be a prime. It’s well known that p splits into two Gaussian primes, p = ππ . Note that it suffices to show ⌊ ⌋ ⌊ ⌋ k k ν ( i ( i − 1)( i − 2) . . . ( i − k + 1)) ≥ ν ( k !) = + + . . . ( ∗ ) π π 2 p p because the similar statement for π will follow. The key claim is the following: t Claim. For any integer t ≥ 1 and n , at least one of numbers i − n − 1 , i − n − 2 , . . . , i − n − p is t divisible by π . t Proof. First, we show that there exists integer r such that π | i − r . To that end, by Hensel’s lemma, t 2 there exists an integer s for which p | s + 1 . Thus, t t π π | ( s − i )( s + i ) . t However, gcd( s − i, s + i ) | 2 , so π must divide either s − i or s + i . In particular, r = s or r = − s work. t t To complete the problem, pick the unique x ∈ { 1 , 2 , . . . , p } such that n + x ≡ r (mod p ) , so i − ( n + x ) ≡ t t i − r (mod p ) and hence divisible by π . Using the claim repeatedly, we find that among numbers i, i − 1 , i − 2 , . . . , i − k + 1 , ⌊ ⌋ ⌊ ⌋ k k • at least are divisible by π (this is by selecting disjoint contiguous block of size p ), p p ⌊ ⌋ k 2 • at least are divisible by π , 2 p ⌊ ⌋ k 3 • at least are divisible by π , 3 p . . • . Using these altogether suffices to prove ( ∗ ) . Impossibility via p -adics Let P ( i ) = a + bi , and note that P ( − i ) = a − bi . Fix some p ≡ 1 mod 4, and consider the p -adic 2 integers Z lying in Q . Note that x + 1 = 0 has a solution in Z , and hence ± i ∈ Z . Now take p p p p a sequence of integers m converging to i in Z , so − m converges to − i . Then since polynomials k p k are continuous, P ( m ) converges to P ( i ) and P ( − m ) converges to P ( − i ) , so P ( m ) + P ( − m ) k k k k and P ( m ) − P ( − m ) converge to 2 x and 2 yi respectively. Finally, since P ( m ) and P ( − m ) are k k k k integers, they have nonnegative p -adic valuation, and so by continuity, 2 x and 2 y have nonegative p -adic valuation. Thus, when written as simplified fractions, a and b cannot have any powers of p in their denominator, as desired. Construction We now show that all of the claimed values are possible. The set of polynomials, P , taking Z to itself is closed under addition and multiplication, and therefore so is the set of possible values of P ( i ) . It clearly − 1 contains Z [ i ] by taking linear polynomials. Thus it suffices to show that p is attainable for every 1 − 1 prime p that is not 1 modulo 4 . 2 is achieved by taking P ( x ) = x ( x − 1)( x − 2)( x − 3)+3 , so we may 4 focus our attention only on the case where p is 3 modulo 4 . It is then further sufficient to show that some − 1 − 1 2 2 − 1 ( a + bi ) p is attainable for a, b ∈ Z not both divisible by p because then ( a − bi ) · ( a + bi ) p = ( a + b ) p is also obtainable and cannot be an integer since − 1 is not a quadratic residue modulo p , so Bézout’s − 1 Theorem shows that p is attainable. Now with this goal in mind, observe that ∣ ( )∣ 2 2 2 2 2 ∣ ∣ i 1 · (1 + 1 ) · . . . · (1 + ( p − 1) ) ∣ ∣ = . ∣ ∣ p p · (2 p − 1) · . . . · 1 has denominator divisible by p , but numerator not divisible by p since again, − 1 is not a quadratic ( ) i − 1 residue modulo p . Hence we can find some integer m so that m = ( a + bi ) p where a and b that p aren’t both divisible by p as desired.