Competition problem — Number theory

Library / /422 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Define the Fibonacci numbers by $F_{0}=0, F_{1}=1, F_{n}=F_{n-1}+F_{n-2}$ for $n \geq 2$ . For how many $n, 0 \leq n \leq 100$ , is $F_{n}$ a multiple of 13?

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

The sequence of remainders modulo 13 begins $0,1,1,2,3,5,8,0$ , and then we have $F_{n+7} \equiv 8 F_{n}$ modulo 13 by a straightforward induction. In particular, $F_{n}$ is a multiple of 13 if and only if $7 \mid n$ , so there are 15 such $n$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.