3

I need to prove that at least one of the first 1000000 Fibonacci numbers is divisible by 1000 and I really don't know how to approach it

Jay
  • 107
uri harel
  • 31
  • Do you mean "... is divisible by 1000" ? – Matti P. Mar 31 '21 at 10:31
  • 2
    I think you can apply the same reasoning as in this answer. – user3733558 Mar 31 '21 at 10:32
  • The usual idea for actually producing one would be to work $\pmod 8$ and $\pmod {125}$ separately. – lulu Mar 31 '21 at 10:34
  • 2
    $F_{750}=2461757021582324272166248155313036893697139996697461509576233211000055607912198979704988704446425834042795269603588522245550271050495783935904220352228801000,$. – Christian Blatter Mar 31 '21 at 10:51
  • Also $F_{1500}, F_{2250}, F_{3000},F_{3750},F_{4500}, F_{5250},F_{6000},F_{6750}, \cdots$ – PierreCarre Mar 31 '21 at 10:56
  • 1
    Any time you're at a loss on how to solve a hard problem, try practicing on a smaller, simpler version of it. Can you show one of the first $100$ Fibonacci numbers is divisible by $10$? (When checking for divisibility by $10$, you can ignore everything but the ones digit. So $1,1,2,3,5,8,13,21,34,55,\ldots$ becomes $1,1,2,3,5,8,3,1,4,5,\ldots$. Keep going till you get a $0$, and then keep going till you get another one. Then look for patterns.) – Barry Cipra Mar 31 '21 at 11:30
  • I think that $F_0=0$ is divisible by any positive integer. I think that the question is actually asking for positive Fibonacci numbers. Also if $N=1000$ then $N^2=1000000$. The result is true for general $N$. – Somos Mar 31 '21 at 11:45

2 Answers2

3

Assume that the $10^6$ first Fibonacci numbers aren't divisble by $1000 \color{blue}{(*)}$, in other words, $$a_n \equiv k \pmod {1000} \qquad \forall n$$ with $k \in {1,...,999}$

From the $(999\times 999+\color{red}2)$ first Fibonacci numbers, we can construct $999\times999+\color{red}1$ couples $(a_n,a_{n+1})$. Applying the Pigeonhole principle where there are $999\times999+1$ pigeons but only $999\times999$ pigeonholes, there exists $(n,m)$ such that $n,m<(999\times 999+2)$ and $$(a_n,a_{n+1}) \equiv (a_m,a_{m+1}) \pmod {(1000,1000)} \tag{1}$$

From $(1)$, we can deduce that the Fibonacci sequence is periodic of order of at most $(m-n)$ (which is less than or equal to $(999\times 999+2)$).

As the two first values of Fibonacci sequence is $(a_1,a_2) = (1,1)$, and because $10^6 >(999\times 999+2)$ then from the periodicity of order at most $(m-n)$ of the sequence, we deduce that $l = (m-n)+\color{red}1 < 10^6$ satisfies $$(a_l,a_{l+1}) \equiv (a_1,a_2) =(1,1) \pmod {(1000,1000)} \tag{1}$$

Hence, $a_{l-1} =a_{l+1}-a_l \equiv 0 \pmod {1000} \implies$ contradiction to $\color{blue}{(*)}$.

We can then conclude that at least one of the $10^6$ first Fibonacci numbers is divisble by $1000$ (Q.E.D).

NN2
  • 15,892
0

This is not really an answer, but was too long for comments. Running a small Wolfram code, the full list of such indexes is:

{750, 1500, 2250, 3000, 3750, 4500, 5250, 6000, 6750, 7500, 8250,
9000, 9750, 10500, 11250, 12000, 12750, 13500, 14250, 15000, 15750,
16500, 17250, 18000, 18750, 19500, 20250, 21000, 21750, 22500, 23250,
24000, 24750, 25500, 26250, 27000, 27750, 28500, 29250, 30000, 30750,
31500, 32250, 33000, 33750, 34500, 35250, 36000, 36750, 37500, 38250,
39000, 39750, 40500, 41250, 42000, 42750, 43500, 44250, 45000, 45750,
46500, 47250, 48000, 48750, 49500, 50250, 51000, 51750, 52500, 53250,
54000, 54750, 55500, 56250, 57000, 57750, 58500, 59250, 60000, 60750,
61500, 62250, 63000, 63750, 64500, 65250, 66000, 66750, 67500, 68250,
69000, 69750, 70500, 71250, 72000, 72750, 73500, 74250, 75000, 75750,
76500, 77250, 78000, 78750, 79500, 80250, 81000, 81750, 82500, 83250,
84000, 84750, 85500, 86250, 87000, 87750, 88500, 89250, 90000, 90750,
91500, 92250, 93000, 93750, 94500, 95250, 96000, 96750, 97500, 98250,
99000, 99750}

See the pattern?

Edit: just noticed I just went as far as $10^5$...

PierreCarre
  • 20,974
  • 1
  • 18
  • 34