Question

The Fibonacci numbers ${\mathbf{F}}_{\mathbf{0}}\mathbf{,}{\mathbf{F}}_{\mathbf{1}}\mathbf{,}\mathbf{.}\mathbf{..}$are given by the recurrence${\mathbf{F}}_{\mathbf{n}\mathbf{+}\mathbf{1}}\mathbf{=}{\mathbf{F}}_{\mathbf{n}}\mathbf{+}{\mathbf{F}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{,}{\mathbf{F}}_{\mathbf{0}}\mathbf{=}\mathbf{0}\mathbf{,}{\mathbf{F}}_{\mathbf{1}}\mathbf{=}\mathbf{1}$. Show that for any$\mathbf{n}\mathbf{\ge }\mathbf{1}\mathbf{,}\mathbf{gcd}\mathbf{(}{\mathbf{F}}_{n+1}\mathbf{,}{\mathbf{F}}_n\mathbf{)}\mathbf{=}\mathbf{1}$.

Short answer

For any $\mathrm{n}\ge 1$,$\gcd ({\mathrm{F}}_{\mathrm{n}+1},{\mathrm{F}}_{\mathrm{n}})=1$

Step-by-step solution

Explain Fibonacci Series

Fibonacci Series is defined as every element of the series is the sum of two previous number of the series. Series starts from 0 and 1.

$\begin{array}{l}{\mathbf{F}}_{n+1}\mathbf{=}{\mathbf{F}}_n\mathbf{+}{\mathbf{F}}_{n-1}\mathbf{forn}\mathbf{=}\mathbf{1}\\ \mathrm{Here},\\ {\mathbf{F}}_n\mathbf{isthe}\mathbf{nthFibonacci}\mathbf{number}\\ {\mathbf{F}}_0\mathbf{=}\mathbf{0}\\ {\mathbf{F}}_1\mathbf{=}{\mathbf{F}}_2\mathbf{=}\mathbf{1}\end{array}$

Calculate the gcd by two methods

$\begin{array}{l}\mathrm{GCD}\mathrm{for}\mathrm{the}\mathrm{Fibonacci}\mathrm{series},\\ \gcd ({\mathrm{F}}_1,{\mathrm{F}}_0)\\ =\gcd (1,0)\\ =1\\ \mathrm{Let}\mathrm{the}\gcd \mathrm{be}\mathrm{correct}\mathrm{forn}=\mathrm{k},\mathrm{that}\mathrm{is}\\ \gcd ({\mathrm{F}}_{\mathrm{k}},{\mathrm{F}}_{\mathrm{k}-1})=1\\ \mathrm{Prove}\mathrm{that}\mathrm{the}\gcd \mathrm{is}\mathrm{also}\mathrm{correct}\mathrm{forn}=\mathrm{k}+1,\mathrm{i}.\mathrm{e}.\\ \gcd ({\mathrm{F}}_{\mathrm{k}+1},{\mathrm{F}}_{\mathrm{k}})=1\\ \gcd ({\mathrm{F}}_{\mathrm{k}+1},{\mathrm{F}}_{\mathrm{k}})\\ =\gcd ({\mathrm{F}}_{\mathrm{k}}+{\mathrm{F}}_{\mathrm{k}-1},{\mathrm{F}}_{\mathrm{k}})\\ =1\\ \mathrm{So},\gcd ({\mathrm{F}}_{\mathrm{k}},{\mathrm{F}}_{\mathrm{k}-1})=1\end{array}$

$\begin{array}{c}\mathrm{Let}\gcd (\mathrm{p},\mathrm{q})=1\mathrm{and}\mathrm{let}\gcd (\mathrm{p}+\mathrm{q},\mathrm{q})=\mathrm{x}.\mathrm{Prove}\mathrm{that}\mathrm{x}=1\\ \gcd (\mathrm{p}+\mathrm{q},\mathrm{q})=\mathrm{x}\\ =\mathrm{x}|\mathrm{p}+\mathrm{qÙx}|\mathrm{q}\\ =\mathrm{x}\left|\right(\mathrm{p}+\mathrm{q})-\mathrm{q}\\ =\mathrm{x}|\mathrm{p}\mathrm{and}\mathrm{since}\mathrm{x}|\mathrm{q}\\ =\mathrm{x}|1\\ =\mathrm{x}=1\\ \gcd (\mathrm{p}+\mathrm{q},\mathrm{q})=1\end{array}$

Thus, $\mathbf{gcd}\mathbf{(}{\mathbf{F}}_{\mathbf{n}\mathbf{+}\mathbf{1}}\mathbf{,}{\mathbf{F}}_{\mathbf{n}}\mathbf{)}\mathbf{=}\mathbf{1}$. Hence proved.