# Some divisibility properties of Fibonacci-like sequences

Here we shall aim to generalise the corollary from the last post, and on the way generalise some other important properties of the Fibonacci sequence, to general Fibonacci-like sequences.

Consider a sequence $\{a_n\}$ with $a_0=0, a_1=1$ and $a_n=ua_{n-1}+va_{n-2}$ for $n\ge 2$, where $u,v\in\mathbb Z$ such that $u^2+4v\neq 0$. Let $\alpha,\beta$ be the roots of $x^2-ux-v=0$. Then

$\displaystyle a_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$.

Let $p$ be an odd prime. Suppose $(\alpha)$ and $(p)$ have a common factor. By Dedekind’s factorisation criterion, $(p)$ is either prime or it factors into two (not necessarily distinct) prime ideals each with norm $p$. In the first case, we must have $(p)\mid (\alpha)$ i.e. $p^2\mid v$, taking ideal norms. In the second case, if one of the prime factors of $(p)$ divides $(\alpha)$, then (again taking norms) $p$ must divide $v$.

So we take $(p,v)=1$ which ensures that $(\alpha)$ and $(p)$ are coprime. Thus we deduce from the general exponent lifting result,

Lemma 1. If $p$ is a prime factor of $a_k$ such that $p\nmid v$, then $p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0$.

Next, recalling the proof of the corollary from last time, we seem to require the condition $(a_m,a_n)=a_{(m,n)}$.

Lemma 2. If $(u,v)=1$, then $(a_m,a_n)=a_{(m,n)}$ for all $m,n$.

Proof. First, it is clear that $(a_m,a_n)/a_{(m,n)}\in\mathcal O_K$, where $K=\mathbb Q(\alpha)$, and that $(a_m,a_n)/a_{(m,n)}\in\mathbb Q$. Thus $(a_m,a_n)/a_{(m,n)}\in\mathbb Z$.

Let $p$ be a prime factor of $(a_m,a_n)$. Then for $m\ge n$,

$\displaystyle p\mid\frac{\alpha^m-\beta^m}{\alpha-\beta}-\frac{\alpha^{m-n}(\alpha^n-\beta^n)}{\alpha-\beta}=\frac{\beta^n(\alpha^{m-n}-\beta^{m-n})}{\alpha-\beta}=\beta^na_{m-n}$.

If $(p)$ and $(\beta^n)$ share a common factor, then (taking ideal norms,) $p\mid v$. Hence $a_n\equiv ua_{n-1}\equiv u^{n-1}\equiv 0\pmod p$, a contradiction as $(u,p)=1$.

Hence $(a_m,a_n)\mid a_{m-n}$ and by the Euclidean algorithm we get $(a_m,a_n)\mid a_{(m,n)}$. Thus $(a_m,a_n)=a_{(m,n)}$, as desired. $\square$

Now we define $k(n)$ to be the least $k$ such that $n\mid a_k$, and we are ready for our generalisation!

Theorem. Let $\{a_n\}$ be given by $a_0=0,a_1=1$ and $a_n=ua_{n-1}+va_{n-2}$ for $n\ge 2$, where $u,v$ are coprime integers such that $u^2+4v\neq 0$. Then for an odd prime $p$ for which $k(p)$ exists,

$p^r\parallel a_{k(p)}\Rightarrow k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}$

Proof. If $p\mid v$, then $p\mid a_{k(p)}-va_{k(p)-2}=ua_{k(p)-1}$. By definition of $k(p)$, $p\nmid a_{k(p)-1}$. Hence $p\mid u$, which is impossible as $(u,v)=1$. Thus $p\nmid v$ and the proof of the corollary in the previous post now applies. $\square$