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