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.

  • $\begingroup$ That is a consequence of $\gcd(F_a,F_b)=F_{\gcd(a,b)}$ that follows from the addition formulas for Fibonacci numbers. $\endgroup$ – Jack D'Aurizio Sep 15 '16 at 14:14

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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