3
$\begingroup$

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$?

$\endgroup$
3
2
$\begingroup$

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}$.

$\endgroup$

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