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


Leave a comment

Filed under Algebra, Number theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s