# If the gcd(s, t)=1, prove $F_s F_t$ divides $F_{st}$ for all s,t > 1 [duplicate]

If the gcd(s, t)=1, prove $$F_s F_t$$ divides $$F_{st}$$ for all s,t > 1

$$F_n$$ is the Fibonacci sequence, such that $$F_n = F_{n-1} + F_{n-2}$$

I know that it needs to be shown that $$F_s F_t\mid F_{st}$$ which has the implication that $$F_{st} = F_s F_tk$$.

I considered that it may be useful to use the theorem that states: the gcd of two fibonacci numbers is also a Fibonacci number with the form $$\gcd(F_s,F_t)= g$$ where $$g= \gcd(s,t)$$ or a Corollary relating to this theorem. But I cannot see how this directly applies to the problem.

Is it valid to say that because a theorem states for any $$s>1, t>1$$, $$F_{st}$$ is divisible by $$F_s$$ then that is an implication for $$F_s F_t\mid F_{st}$$ because the $$\gcd(s,t) =1$$?

• – lab bhattacharjee Nov 19 '19 at 8:00
• I did mention this Theorem in my original question, but I am confused about how to apply it in this situation. Thanks for your response! – math1234567890 Nov 19 '19 at 8:19
• Proving that $n|m\implies f_n|f_m$ – mathlove Nov 19 '19 at 8:48

Using that $$\gcd(F_m,F_n) = F_{\gcd(m,n)}$$ for all $$n,n \in \mathbb{Z_{\gt 2}}$$, as you've basically stated and as the link of GCD of Fibonacci Numbers which lab bhattacharjee's question comment indicates, you get for $$s,t \gt 2$$ that
$$\gcd(F_{st},F_{s}) = F_{\gcd(st,s)} = F_{s} \tag{1}\label{eq1A}$$
$$\gcd(F_{st},F_{t}) = F_{\gcd(st,t)} = F_{t} \tag{2}\label{eq2A}$$
$$\gcd(F_{s},F_{t}) = F_{\gcd(s,t)} = F_{1} = 1 \tag{3}\label{eq3A}$$
Note \eqref{eq1A} gives that $$F_{s} \mid F_{st}$$ and \eqref{eq2A} gives that $$F_{t} \mid F_{st}$$. Since \eqref{eq3A} shows that $$F_{s}$$ and $$F_{t}$$ are relatively prime, this means that $$F_{s}F_{t} \mid F_{st}$$ (e.g., as shown in if $$b$$ divides $$ck$$ and $$b$$ and $$c$$ are relatively prime, then $$b$$ must divides $$k$$).
This just leaves the case where one of $$s$$ or $$t$$ is $$2$$. WLOG, let $$s = 2$$ so $$t$$ is odd. Since $$F_2 = 1$$, the question is asking to prove that $$F_{t} \mid F_{2t}$$ for all odd $$t$$. For this, you can use Proving that $$n|m\implies f_n|f_m$$ that mathlove's question comment states, since $$t \mid 2t$$ so $$F_t \mid F_{2t}$$.