HMMT 二月 2025 · 团队赛 · 第 9 题
HMMT February 2025 — Team Round — Problem 9
题目详情
- [60] Let Z be the set of integers. Determine, with proof, all primes p for which there exists a function f : Z → Z such that for any integer x , • f ( x + p ) = f ( x ) and • p divides f ( x + f ( x )) − x . 2 2 2
解析
- [60] Let Z be the set of integers. Determine, with proof, all primes p for which there exists a function f : Z → Z such that for any integer x , • f ( x + p ) = f ( x ) and • p divides f ( x + f ( x )) − x . Proposed by: Marin Hristov Hristov Answer: p = 5 and all primes p ≡ ± 1 (mod 5) Solution: We work in F , treating f as a map from F to itself. Clearly, p = 2 doesn’t work. For p p p > 2 such that 5 is a quadratic residue mod p , as well as p = 5 itself, there exists some α such that 2 (2 α + 1) ≡ 5 (mod p ). Taking f ( x ) = αx then works because 1 2 2 f ( x + f ( x )) − x = ( α + α − 1) x = (2 α + 1) − 5 x ≡ 0 (mod p ) . 4 To prove no other primes satisfy the conditions in the problem statement, note that f is surjective, as for any x , f ( x + f ( x )) = x . As F is finite, f is bijective. Plugging in x = f ( y ) yields p f ( f ( y ) + f ( f ( y ))) = f ( y ) = ⇒ f ( y ) + f ( f ( y )) = y. Since f is bijective, there exists z ∈ F such that f ( z ) = 0, then z = f ( z + f ( z )) = f ( z ) = 0. Therefore, p f (0) = 0. This is the only fixed point, as any fixed point d would satisfy d = f ( d ) + f ( f ( d )) = 2 d , which is impossible if d ̸ = 0. Hence the remaining residues form nontrivial cycles y , f ( y ), f ( f ( y )), etc. If the cycle containing y is of length n , then − 1 f ( y ) = y + f ( y ) , − 2 − 1 f ( y ) = f ( y ) + y = 2 y + f ( y ) , . . . − ( n − 1) f ( y ) = f ( y ) = F y + F f ( y ) , (by induction) n n − 1 y = F y + F f ( y ) , n +1 n where F is the k -th Fibonacci number. As y ̸ = 0 and f ( y ) ̸ = 0, the last two equations tell us k (1 − F ) f ( y ) (1 − F ) y n − 1 n +1 2 F ≡ ≡ ( F − 1)( F − 1) (mod p ) . n +1 n − 1 n y f ( y ) Let A = F − 1 and B = F − 1 for brevity. The last equation becomes n +1 n − 1 1 2 2 2 2 2 ( A − B ) ≡ AB ≡ (( A + B ) − ( A − B ) ) (mod p ) = ⇒ ( A + B ) ≡ 5( A − B ) (mod p ) . 4 As 5 is not a quadratic residue, this implies F ≡ F ≡ 1 (mod p ). Hence, if d is the smallest n +1 n − 1 positive integer such that F ≡ 0 (mod p ) and F ≡ 1 (mod p ), then the Fibonacci sequence is d d +1 periodic modulo p with period d , so d | n . The sum of all cycle lengths (excluding the fixed point 0) is p − 1, so d | p − 1. The following well-known lemma will give us a contradiction. Lemma 1. If 5 is not a quadratic residue modulo a prime p , then p ∤ F . p − 1 Proof 1. Recall Binet’s formula, ! ! √ p − 1 √ p − 1 1 1 + 5 1 − 5 √ F = − . p − 1 2 2 5 p − 1 Multiplying both sides by 2 and expanding via the binomial theorem, we have p − 3 2 X p − 1 p − 1 k 2 F = 2 5 . p − 1 2 k + 1 k =0 p − 1 2 k +1 However, ≡ ( − 1) ≡ − 1 (mod p ) for all k , so 2 k +1 p − 3 p − 1 2 X 2 5 − 1 k p | F if and only if p 5 = . p − 1 5 − 1 k =0 p − 1 2 Therefore p | F if and only if 5 ≡ 1 (mod p ), which doesn’t hold if 5 is not a quadratic residue p − 1 modulo p , as desired. √ √ √ p Proof 2. Work in F 2 = F [ 5]. Since 5 is not a quadratic residue, we get that ( 5) = − 5. Using p p p p p the fact that ( a + b ) = a + b (because all other terms have coefficient divisible by p ), we get that ! ! ! √ p √ √ p − 1 √ 2 √ 1 + 5 1 − 5 1 + 5 1 − 5 3 − 5 = = ⇒ = = . 2 2 2 2 2 √ √ p − 1 1 − 5 3+ 5 Similarly, = . Hence, by Binet’s formula, 2 2 ! ! √ p − 1 √ p − 1 1 1 + 5 1 − 5 √ F = − p − 1 2 2 5 ! √ √ 1 3 − 5 3 + 5 = √ − = − 1 , 2 2 5 so it is not divisible by p . Hence, F ̸ ≡ 0 (mod p ) if 5 is not a quadratic residue modulo p , which contradicts d | p − 1 above. p − 1 This completes the solution. 2 2 2