HMMT 二月 2003 · 冲刺赛 · 第 6 题
HMMT February 2003 — Guts Round — Problem 6
题目详情
- [6] Define the Fibonacci numbers by F = 0, F = 1, F = F + F for n ≥ 2. For 0 1 n n − 1 n − 2 how many n , 0 ≤ n ≤ 100, is F a multiple of 13? n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND √ √ √
解析
- Define the Fibonacci numbers by F = 0, F = 1, F = F + F for n ≥ 2. For 0 1 n n − 1 n − 2 how many n , 0 ≤ n ≤ 100, is F a multiple of 13? n 1 Solution: 15 The sequence of remainders modulo 13 begins 0 , 1 , 1 , 2 , 3 , 5 , 8 , 0, and then we have F ≡ 8 F modulo 13 by a straightforward induction. In particular, F is a multiple n +7 n n of 13 if and only if 7 | n , so there are 15 such n . √ √ √