Track / Stage 6 / 131 of 400 #1131 of 1964

Problem 1131

National olympiad, first round

Number theory Difficulty 6.2 Prove it

04.2. Let $f_{1}=0, f_{2}=1$ , and $f_{n+2}=f_{n+1}+f_{n}$ , for $n=1$ , 2, ..., be the Fibonacci sequence. Show that there exists a strictly increasing infinite arithmetic sequence none of whose numbers belongs to the Fibonacci sequence. [A sequence is arithmetic, if the difference of any of its consecutive terms is a constant.]

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution. The Fibonacci sequence modulo any integer $n>1$ is periodic. (Pairs of residues are a finite set, so some pair appears twice in the sequence, and the sequence from the second appearance of the pair onwards is a copy of the sequence from the first pair onwards.) There are integers for which the Fibonacci residue sequence does not contain all possible residues. For instance modulo 11 the sequence is $0,1,1,2,3,5,8,2,10,1$ , $0,1,1, \ldots$ Wee see that the number 4 is missing. It follows that no integer of the form $4+11 k$ appears in the Fibonacci sequence. But here we have an arithmetic sequence of the kind required.

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