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.

  • $\begingroup$ Not sure this is clear. $F_0=1=F_1$ and clearly $1\,|\,1000$. But, then, I think you meant something else, no? $\endgroup$ – lulu Jan 11 at 0:09
  • $\begingroup$ 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). $\endgroup$ – lulu Jan 11 at 0:19
  • $\begingroup$ Yes. I have already corrected. Sorry. $\endgroup$ – pawelK Jan 11 at 0:21
  • $\begingroup$ 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. $\endgroup$ – lulu Jan 11 at 0:23
  • $\begingroup$ Do you mean $1000$ divides $F_a,\ $ or $\ F_a$ divides $1000?\ \ $ $\endgroup$ – Bill Dubuque Jan 11 at 0:24

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$

  • $\begingroup$ "just by computation" hides a lot. Also, this does not use the pigeon hole principle. $\endgroup$ – marty cohen Jan 11 at 2:25
  • 1
    $\begingroup$ @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. $\endgroup$ – Ross Millikan Jan 11 at 3:02
  • $\begingroup$ I agree that is true. Look up divisibility sequences. $\endgroup$ – marty cohen Jan 11 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.