# GCD of Consecutive Integers of General Fibonacci Sequence

## Theorem

Let $\FF = \sequence {a_n}$ be a general Fibonacci sequence generated by the parameters $r, s, t, u$:

- $a_n = \begin{cases}

r & : n = 0 \\ s & : n = 1 \\ t a_{n - 2} + u a_{n - 1} & : n > 1 \end{cases}$

Let:

- $d = \gcd \set {r, s}$

where $\gcd$ denotes greatest common divisor.

Let $f = \gcd \set {a_m, a_{m - 1} }$ for some $m \in \N$.

Let $\gcd \set {f, t} = 1$.

Then:

- $f \divides d$

## Proof

Proof by induction:

Let $\map P m$ be the proposition:

- $\gcd \set {f_m, t} = 1 \implies f_m = d$

where $f_m = \gcd \set {a_m, a_{m - 1} }$.

For clarity, we have indexed $f$.

### Basis for the Induction

For $m = 1$:

- $f_1 = \gcd \set {a_1, a_0} = \gcd \set {s, r} = d$

This is the basis for the induction.

### Induction Hypothesis

Now we assume that $\map P k$ is true for some $k \in \N$.

In other words, this is our induction hypothesis:

- $\gcd \set {f_k, t} = 1 \implies f_k = d$

where $f_k = \gcd \set {a_k, a_{k - 1} }$.

Now we need to show that $\map P {k + 1}$ is true, that is:

- $\gcd \set {f_{k + 1}, t} = 1 \implies f_{k + 1} = d$

where $f_{k + 1} = \gcd \set {a_{k + 1}, a_k}$.

### Induction Step

This is our induction step:

\(\ds f_{k + 1}\) | \(=\) | \(\ds \gcd \set {a_{k + 1}, a_k}\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {t a_{k - 1} + u a_k, a_k}\) | Definition of $\sequence {a_n}$ | |||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {t a_{k - 1}, a_k}\) | GCD with Remainder | |||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {t, a_k} \gcd \set {a_{k - 1}, a_k}\) | GCD with One Fixed Argument is Multiplicative Function | |||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {t, a_k} f_k\) |

Suppose that $\gcd \set {f_{k + 1}, t} = 1$.

Then:

\(\ds 1\) | \(=\) | \(\ds \gcd \set {f_{k + 1}, t}\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {\gcd \set {t, a_k}, t}\) | Divisor of One of Coprime Numbers is Coprime to Other | |||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {t, \gcd \set {t, a_k} }\) | Greatest Common Divisor is Symmetric | |||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {\gcd \set {t, t}, a_k}\) | Greatest Common Divisor is Associative | |||||||||||

\(\ds \) | \(=\) | \(\ds \gcd \set {t, a_k}\) | GCD of Integer and Divisor |

By the two results above, we have:

- $f_{k + 1} = \gcd \set {t, a_k} f_k = f_k$

so we have $\gcd \set {f_k, t} = \gcd \set {f_{k + 1}, t} = 1$ as well.

By the induction hypothesis and Modus Ponendo Ponens:

- $f_k = d$

and thus:

- $f_{k + 1} = f_k = d$

so $\map P {k + 1}$ is true.

By the Principle of Mathematical Induction, $\map P m$ is true for all $m \in \N$.

Hence the result.

$\blacksquare$

## Sources

- 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {2-2}$ Divisibility: Exercise $12 \ \text{(b)}$