If $\gcd(a,b) \mid c$, then $\gcd(F_a, F_b) \mid F_c$, where $F_n$ is the nth fibonacci number

Question

Let $a$, $b$ and $c$ be natural numbers. Show that if $\gcd(a,b) \mid c$, then the equation \begin{equation} F_a \cdot x + F_b \cdot y = F_c \end{equation} has an integer solution. Here, $F_n$ is the nth fibonacci number.

Now, saying that the equation above has an integer solution is the same as saying $\gcd(F_a,F_b) \mid F_c$, right? So what we really want to show is $\gcd(a,b) \mid c \Rightarrow \gcd(F_a,F_b) \mid F_c$.

Set $\gcd(a,b) = d$ and $\gcd(F_a,F_b) = D$. Then, if $d\mid c$ and $D \mid F_c$ we can write $c = dq_1$ and $F_c = Dq_2$ for any integer $q_1$ and $q_2$ ($q_2$ should be positive).

We have that $\gcd(F_a, F_b) = F_{\gcd(a,b)}$, or $D = F_d$. Using the expression for $F_c$ above, we see that $F_c = F_dq_2 \Rightarrow F_d \mid F_c$. Does this mean that $F_d$ is also a solution to the equation? In that case, how does that really help me?

I just feel like I'm going in circles, and I think I might be tackling this problem the wrong way. I also find it very difficult to connect the fibonacci numbers to the natural numbers.

Answer 1

Hint: $$\gcd(F_a,F_b)=F_{\gcd(a,b)}$$

Proof: We have $F_{n+2}=F_{n+1}+F_n=F_n+2F_{n-1}=3F_{n-1}+2F_{n-2}=\ldots$, hence by induction $$ F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n} $$ and $$ \gcd(F_{n+k},F_{n}) = \gcd(F_k F_{n+1},F_n) = \gcd(F_n,F_k) $$ since $F_{n}$ and $F_{n+1}$ are coprime. By applying induction again the claim follows.