HMMT 二月 2017 · ALGNT 赛 · 第 9 题

HMMT February 2017 — ALGNT Round — Problem 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

解析

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 Fibonacci 2 numbers mod 127. Let p = 127. We work in F for the remainder of this proof. Let α and β be the p n n α − β 2 p roots of x − x − 1. Then we know that F = . Note that since x → x is an automorphism n α − β p p and since automorphisms cycle the roots of a polynomial we have that α = β and β = α . Then p p α − β αβ − βα F = = − 1 and F = = 0 and similarly we obtain F = 1 and F = 0. Thus p 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 .