HMMT February

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. Fractions can be typed as 3/2, and spacing doesn't matter.

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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.