Monthly Archives: August 2013

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

A generalisation of ‘lifting the exponent’

Lifting the exponent is a popular result in elementary number theory. It basically says that if \alpha,\beta\in\mathbb Z and a_n=(\alpha^n-\beta^n)/(\alpha-\beta), then for an odd prime p coprime to \alpha,\beta and for r\ge 1,

Theorem 1. (Lifting the exponent) p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0.

Here, as usual, p^r\parallel x means that p^r\mid x but p^{r+1}\nmid x.

We shall generalise this to general rings of algebraic integers. In the following, K will denote an algebraic number field and \mathcal O_K its ring of integers. Let \alpha,\beta\in\mathcal O_K such that the ideals (\alpha), (\beta) are coprime to (p), and a_n\in\mathbb Z\ \forall n.

Theorem 2. p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0.

Proof. We proceed by induction on n. The base case n=0 is clear. Suppose that the assertion holds for n-1. We want to show that p^{n+r}\parallel a_{kp^n}, that is,

\displaystyle p^{n+r}\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha-\beta}=a_{kp^{n-1}}\cdot\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}

By hypothesis, p^{n+r-1}\parallel a_{kp^{n-1}}. So we need to show that \displaystyle p\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}.

Let c=\alpha^{kp^{n-1}}, d=\beta^{kp^{n-1}}. We want to show that \displaystyle p\parallel\frac{c^p-d^p}{c-d}.

Since p\mid a_k, we have a_k\in (p). Hence \alpha^k-\beta^k=(\alpha-\beta)a_k\in (p), i.e. \alpha^k\equiv\beta^k\pmod p. Hence c\equiv d\pmod p. Let c=d+\mu p for some \mu\in\mathcal O_K. Then

\displaystyle\frac{c^p-d^p}{c-d}=\frac{(d+\mu p)^p-d^p}{\mu p}=\frac{p\cdot d^{p-1}\mu p+\ldots}{\mu p}\equiv pd^{p-1}\pmod{p^2}.

If this is 0, then (p)\mid (d)^{p-1}, which is impossible by unique factorisation as (p) and (d) are coprime. \square

Corollary. Let \{F_n\} be the Fibonacci sequence. Then

p^r\parallel F_{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}

(Refer to this post for notation.)

Proof. Take \alpha=\varphi=\frac{1+\sqrt 5}{2}, \beta=\bar\varphi=\frac{1-\sqrt 5}{2} (with K=\mathbb Q(\sqrt 5) and \mathcal O_K=\mathbb Z[\varphi]) and let k=k(p). We proceed by induction on n. Suppose p^{n+r}\mid F_j for some j<kp^n. By hypothesis, k(p^{n+r-1})=kp^{n-1} so p^{n+r-1}\mid p^{n+r}\mid F_j\Rightarrow kp^{n-1}\mid j<kp^n. Then 1\le \frac{j}{kp^{n-1}}<p, so \gcd(\frac{j}{kp^{n-1}},p)=1, i.e. \gcd(j,kp^n)=kp^{n-1}. Hence \gcd(F_{kp^n},F_j)=F_{kp^{n-1}} which implies p^{n+r}\mid F_{kp^{n-1}}, a contradiction. \square


Filed under Algebra, Number theory

More on irrationality

Recall some of the irrationality criteria that we discussed in the last post. We showed that

Proposition 1. Let a_1,a_2,\dots be a sequence of non-zero integers such that

(\dagger)\qquad\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots exists, and

(\ddagger)\qquad\displaystyle \frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots\to 0 as n\to\infty.

Then S is irrational.

In particular,

Proposition 2. If a_1,a_2,\dots is a sequence of non-zero integers such that |a_1|\le |a_2|\le\dots and \displaystyle\lim_{n\to\infty}|a_n|=\infty, then

\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots

exists and is irrational.

Having proven these, it is natural to ask whether every irrational number can have such a representation. Interestingly, work has already been done on this. The Engel expansion of a positive real number x is a unique expansion of the form

\displaystyle x=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots

where \{a_n\} is a non-decreasing sequence of positive integers. Every positive rational number has a finite Engel expansion, and x is irrational if an only if this expansion is infinite.

In this post we shall slightly improve our previous results.

Proposition 3. Let a_1,a_2,\dots and b_1,b_2,\dots be sequences of non-zero integers such that

(\dagger')\qquad\displaystyle S=\frac{b_1}{a_1}+\frac{b_2}{a_1a_2}+\frac{b_3}{a_1a_2a_3}+\dots exists, and

(\ddagger')\qquad\displaystyle \frac{b_{n+1}}{a_{n+1}}+\frac{b_{n+2}}{a_{n+1}a_{n+2}}+\frac{b_{n+3}}{a_{n+1}a_{n+2}a_{n+3}}+\dots\to 0 as n\to\infty.

Then S is irrational.

Proof. The same argument in the proof of Proposition 1 applies. \square

Proposition 4. If a_1,a_2,\dots and b_1,b_2,\dots are sequences of non-zero integers such that |a_1|\le |a_2|\le\dots and \displaystyle\lim_{n\to\infty}|b_n/a_n|=0 then

\displaystyle S=\frac{b_1}{a_1}+\frac{b_2}{a_1a_2}+\frac{b_3}{a_1a_2a_3}+\dots

exists and is irrational.

Proof. It suffices to show that (\dagger') and (\ddagger') above hold.

Convergence follows easily using the ratio test. So we show that (\ddagger') holds.

We have, for sufficiently large n,




\displaystyle =\left|\frac{b_{n+1}}{a_{n+1}}\right|+\frac{1}{|a_{n+1}|-1}


\displaystyle\le 3\left|\frac{b_{n+1}}{a_{n+1}}\right|\to 0 as n\to\infty.

So (\ddagger') holds, as desired. \square

As an immediate corollary we get:

Corollary 1. Let f:\mathbb R\to\mathbb R have an infinite Taylor expansion about x=0 that converges for |x|\le 1. If f^{(n)}(0)\in\mathbb Z\,\forall n\ge 0 and f^{(n)}(0)=o(n) as n\to\infty, then f(1/k) is irrational \forall k\in\mathbb Z\backslash\{0\}.

Taking, for example, f(x)=\rho\exp(x)+\mu\sin(x)+\nu\cos(x) yields:

Corollary 2. Let \rho,\mu,\nu be integers, not all zero. Then \rho\exp(1/k)+\mu\cos(1/k)+\nu\sin(1/k) is irrational \forall k\in\mathbb Z\backslash\{0\}.

In particular, e\pm\sin 1, e\pm\cos 1,\sin 1\pm\cos 1, e\pm\sin 1\pm\cos 1  etc are all irrational.

Leave a comment

Filed under Analysis, Number theory