# 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$

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. 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. Then $1\le \frac{j}{kp^{n-1}}, 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}}+\frac{b_{n+2}}{a_{n+1}a_{n+2}}+\frac{b_{n+3}}{a_{n+1}a_{n+2}a_{n+3}}+\dots\right|$

$\displaystyle\le\left|\frac{b_{n+1}}{a_{n+1}}\right|+\left|\frac{b_{n+2}}{a_{n+2}}\right|\frac{1}{|a_{n+1}|}+\left|\frac{b_{n+3}}{a_{n+3}}\right|\frac{1}{|a_{n+1}a_{n+2}|}+\dots$

$\displaystyle\le\left|\frac{b_{n+1}}{a_{n+1}}\right|+\frac{1}{|a_{n+1}|}+\frac{1}{|a_{n+1}|^2}+\frac{1}{|a_{n+1}|^3}+\dots$

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

$\displaystyle\le\left|\frac{b_{n+1}}{a_{n+1}}\right|+\frac{2}{|a_{n+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.