Let f0,f1,... be the Fibonacci sequence: f0=f1=1,fn=fn−1+fn−2 if n≥2. Determine all possible positive integers n so that there is a positive integer a such that fn≤a≤fn+1 and that a(1f1+1f1f2+⋯+1f1f2...fn) is an integer.
Problem
Source: SMO 2015 open
Tags: number theory, Fibonacci sequence
01.04.2018 09:51
Expanding the above expression a(f2f3..fn+f3..fn+⋯fn−1fn+fn+1f1f2..fn ⟹fn|a(f2f3..fn+f3..fn+⋯+fn−1fn+fn+1) ⟹fn|a for n≥3, and moreover, 2fn>fn+1 as fn+1=fn+fn−1 Hence we can deduce a=fn for n≥3 We get that a gets cancelled. And fn−1|fn+1
Now using our claim we get n is even. We also getfn−2|fn−1fn+fn+1 Using again our claim f2n−1=fnfn−2+(−1)n−1 as n is even we get f2n−1≡−1(modfn−2)−(1)
But we know that (fn,fn+1)=1 So we are only left with cases n∈1,2,3 When n=1 we have a∈1,2. When n=2 we have a∈2 When n=3 we have a∈3◼
10.07.2022 16:24
a(1f1+1f1f2+⋯+1f1f2...fn)=a(f2f3…fn+f3f4…fn+…+fn+1f1f2...fn)so f1f2...fn∣a(f2f3…fn+f3f4…fn+…+fn+1).In particular fn∣a(f2f3…fn+f3f4…fn+…+fn+1)but since f_2 f_3 \ldots f_n+ f_3f_4 \ldots f_n + \ldots + f_n + 1 \equiv 1 \pmod {f_n} implies \gcd(f_2 f_3 \ldots f_n+ f_3f_4 \ldots f_n + \ldots + f_n + 1,\ f_n) = 1, we must have f_n \mid a. But a \leq f_{n+1} < 2 f_n, so we must have a = f_n. This implies f_1f_2...f_{n-1} \mid f_2 f_3 \ldots f_n+ f_3f_4 \ldots f_n + \ldots + f_n + 1.so f_{n-1} \mid 1 so n-1 = 0 \text{ or } 1. We check that n = 1,2 both yield solutions.