# Fibonacci sequence and Pigeonhole principle

Consider set $$A:= \{F_{n} \mid n, \, 1 \leq n \leq 1000002\}$$ where $$F_{n}$$ denotes the $$n$$th Fibonacci number.

Prove that exist at least two numbers $$F_a$$ and $$F_b$$, such that $$F_a,F_b \in A$$ and $$F_a$$, $$F_b$$ are divisible by $$1000$$.

I trying to use the Dirichlet's box principle, but I have problem, how to define pigeonhole.

• Not sure this is clear. $F_0=1=F_1$ and clearly $1\,|\,1000$. But, then, I think you meant something else, no? – lulu Jan 11 at 0:09
• Is it possible that you meant to require $1000\,|\,F_a$? If so, then note that $1000=2^3\times 5^3$ so try to find indices $i,j$ for which $8\,|\,F_i$ and $125\,|\,F_j$ and then use the divisibility properties of the Fibonacci numbers. (Note: the divisibility properties look much better if you use the convention $F_0=0,F_1=1$ instead of the convention I used earlier). – lulu Jan 11 at 0:19
• Yes. I have already corrected. Sorry. – pawelK Jan 11 at 0:21
• I don't see any correction. Anyway, assuming I guessed your intent correctly, my hint should lead to a solution pretty quickly. Not sure it's a pencil and paper solution, but it is close. – lulu Jan 11 at 0:23
• Do you mean $1000$ divides $F_a,\$ or $\ F_a$ divides $1000?\ \$ – Bill Dubuque Jan 11 at 0:24

## 1 Answer

Every sixth element is divisible by $$8$$ and every $$125^{th}$$ is divisible by $$125$$, just by computation. Then every $$750^{th}$$ is divisible by $$1000$$

Note that we just have to find the first element divisible by any prime power. The next number after that may not be $$1$$, but the recurrence is linear. In this example, $$F_7\equiv 5 \pmod 8$$, but the next block is just the first block multiplied by $$5$$ and $$0 \cdot 5=0$$

• "just by computation" hides a lot. Also, this does not use the pigeon hole principle. – marty cohen Jan 11 at 2:25
• @martycohen: I don't think it hides anything. I just made a spreadsheet and I justified why once you find one zero it will repeat at that period. I agree it does not use pigeonhole. I don't have a good pigeonhole approach. It looks like we are supposed to use $1000^2=1000000$ but I don't see how to show there isn't a correlation that prevents a solution. – Ross Millikan Jan 11 at 3:02
• I agree that is true. Look up divisibility sequences. – marty cohen Jan 11 at 3:04