HMMT 二月 2017 · ALGNT 赛 · 第 9 题

英文解析

9. The Fibonacci sequence is defined as follows: F = 0, F = 1, and F = F + F for all integers
   0 1 n n − 1 n − 2
   n ≥ 2. Find the smallest positive integer m such that F ≡ 0 (mod 127) and F ≡ 1 (mod 127).
   m m +1
   Proposed by: Sam Korsky
   Answer: 256
   First, note that 5 is not a quadratic residue modulo 127 . We are looking for the period of the Fibonaccinumbers mod 127. Let p = 127. We work in F for the remainder of this proof. Let α and β be the 2
   n npα − β
   2 proots of x − x − 1. Then we know that F = . Note that since x → x is an automorphismα − βnp pand since automorphisms cycle the roots of a polynomial we have that α = β and β = α . Thenp pα − β αβ − βα
   F = = − 1 and F = = 0 and similarly we obtain F = 1 and F = 0. Thusp p +1 2 p +1 2 p +2
   α − β α − βsince 2 p + 2 is a power of 2 and since the period does not divide p + 1, we must have the answer is
   2 p + 2 = 256 .