# Tag Archives: fibonacci number

## Factoring Fibonacci Numbers

I just wrote a C program based on this note that can decide whether the Fibonacci number $F_p$ is prime for a prime index $p$. (Recall that $F_n$ is composite when $n>4$ is composite.) I had written a MATLAB program some years ago and since I can’t access MATLAB on my current computer I decided to rewrite it in C. The program can compute the smallest prime factor of $F_p$ for all primes $p\le 93$ on a 64-bit system.

EDIT: I’ve improved my program slightly so that now it works for $p\le 130$. (Note: $F_{130}=659,034,621,587,630,041,982,498,215$.) The new code looks somewhat ugly so I won’t post it here.

EDIT (07/05/2020): I implemented this, along with other functionalities, in Python here.

#include <stdio.h>

int isprime(unsigned long long n) {
int i, ans=1;
for (i=2; i*i<=n; i++) {
if(n%i==0){
ans=0;
break;
}
}
return ans;
}

int main() {
int p;
printf("Enter an odd prime number: ");
scanf("%d", &p);

unsigned long long prev=1, cur=1, next, ind=2;
while (ind<p) {
next=prev+cur;
prev=cur;
cur=next;
ind++;
}

unsigned long long Fp, P, Q;
Fp=cur;
P=4*p+1;
Q=2*p-1;
while (Q*Q<=Fp) {
if (isprime(Q)==1 && ((Q%10)-3)*((Q%10)-7)==0 && Fp%Q==0){
printf("The smallest prime factor of Fibonacci(%d)=%llu is %llu.", p, Fp, Q);
return 0;
}
else if (isprime(P)==1 && ((P%10)-1)*((P%10)-9)==0 && Fp%P==0){
printf("The smallest prime factor of Fibonacci(%d)=%llu is %llu.", p, Fp, P);
return 0;
}
P=P+4*p;
Q=Q+4*p;
}
printf("Fibonacci(%d)=%llu is prime.", p, Fp);
return 0;
}

Filed under Number Theory

## Finite Automata 3: Non-Automatic Sets

The key ingredients in our proof of the special case of Cobham’s theorem were the Pumping Lemma and the following fact:

$(*)\qquad [ab^{n+1}c]_q-q^{|b|}[ab^nc]_q=\text{constant}$

We can formally put them together into the following lemma:

Lemma 1. If $S\subseteq\mathbb N$ is an infinite automatic set, then there exist distinct $s_0,s_1,\ldots\in S$ and integers $A>1$ and $B$ such that $s_{n+1}=As_n+B$ for all $n$.

Proof. Say $S$ is $q$-automatic. By the pumping lemma we can take $s_n=[ab^nc]_q$ for some $a,b,c\in\Sigma_q^*$ with $|b|\ge 1$. Note that these are distinct as we don’t allow leading zeros. The conclusion now follows from $(*)$. $\square$

Lemma 1 can be a powerful tool in proving that sets are not automatic, because it transforms a question from automata theory into the language of simple unary recurrences. For instance, we can use it to easily prove the following theorem of Minsky and Papert:

Theorem 1 (Minsky and Papert, 1966). The set of prime numbers is not automatic.

We are actually able to prove the following stronger result:

Theorem 2 (Schützenberger, 1968). An infinite set of prime numbers is not automatic.

Proof. Assume the contrary. Then by lemma 1 there exist distinct prime numbers $p_1,p_2,\dots$ and integers $A>1$ and $B$ such that $p_{n+1}=Ap_n+B$ for all $n\ge 1$. Then

$p_{n+j}\equiv B(A^{j-1}+\dots +A+1)\pmod{p_n}$

for all $j,n\ge 1$. Now pick $n$ large enough so that $p_n\nmid A(A-1)$. Then

$\displaystyle p_{n+p_n-1}\equiv\frac{B(A^{p_n-1}-1)}{A-1}\equiv 0\pmod{p_n}$

by Fermat’s little theorem, a contradiction. $\square$

Note that lemma 1 implies that any set whose elements increase very rapidly cannot be automatic. To put it formally:

Theorem 3. Let $f:\mathbb N\to\mathbb N$ such that $f(n+1)/f(n)\to\infty$ as $n\to\infty$. Then the set $\{f(1),f(2),f(3),\dots\}$ is not automatic.

Proof. Assume the contrary. Then there exist integers $0 such that $f(s_{n+1})=Af(s_n)+B$ for all $n$, where $A>1$ and $B$ are fixed integers. Then $f(s_{n+1})/f(s_n)\to A$ as $n\to\infty$, a contradiction. $\square$

Corollary 1. The set $\{1!,2!,3!,\dots\}$ of factorials is not automatic.

Proof. Take $f(n)=n!$ in theorem 3. $\square$

Corollary 2. The set $\{2^{2^0}+1,2^{2^1}+1,2^{2^2}+1,\dots\}$ of Fermat numbers is not automatic.

Proof. Take $f(n)=2^{2^{n-1}}+1$ in theorem 3. $\square$

It is possible to use lemma 1 in other ways to show that sets are not automatic. For example:

Theorem 4. Let $f:\mathbb N\to\mathbb N$ such that $f(n+1)/f(n)\to\alpha$ as $n\to\infty$, where $\alpha$ is a real number such that $\alpha^m\not\in\mathbb N$ for any $m\in\mathbb N$. Then the set $\{f(1),f(2),f(3),\dots\}$ is not automatic.

Proof. Assume the contrary. Then by lemma 1 there exist distinct positive integers $s_0,s_1,\dots$ such that $f(s_{n+1})=Af(s_n)+B$ for all $n$, where $A>1$ and $B$ are fixed integers. Now

$\displaystyle\lim_{n\to\infty}\frac{f(n+m)}{f(n)}=\alpha^{m}$

for all $m\in\mathbb N$. Therefore, as $f(s_{n+1})/f(s_n)\to A$, it follows that $A=\alpha^m$ for some $m\in\mathbb N$. But this is impossible, as $\alpha^m\not\in\mathbb N$ for any $m\in\mathbb N$. $\square$

Corollary 3. The set $\{0,1,1,2,3,5,\dots\}$ of Fibonacci numbers is not automatic.

Proof. Let $F_n$ denote the $n$-th Fibonacci number. Note that $F_{n+1}/F_n\to\varphi=(1+\sqrt 5)/2$ as $n\to\infty$, and that $\varphi^m=F_m\varphi+F_{m-1}\not\in\mathbb N$ for all $m\in\mathbb N$. So the result follows by theorem 4. $\square$

In the exact same manner we also get:

Corollary4. The set $\{2,1,3,4,7,11,\dots\}$ of Lucas numbers is not automatic.

Filed under Analysis, Combinatorics, Number Theory

## 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 the following from Theorem 2 of this post.

Lemma 1. If $p$ is a prime factor of $a_k$ such that $p\nmid v$, then for all $n\ge 0$,

$p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}$.

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)}\implies 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 the following.

Theorem 1. (Lifting the Exponent) Let $\alpha,\beta\in\mathbb Z$ and put

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

Then for an odd prime $p$ coprime to $\alpha,\beta$, and for $r\ge 1$,

$p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}$

for all integers $n\ge 0$.

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

We generalize Theorem 1 to general rings of algebraic integers.

Theorem 2. Let $K$ be 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=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$

is an integer for all integers $n\ge 0$. Then

$p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}$

for all integers $r\ge 1$ and $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+\cdots}{\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)}\implies 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\implies 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

## An Irrationality Criterion

Recall Corollary 4 from this post:

Corollary 4. If $S$ is a subgroup of $(\mathbb R,+)$, then the following are equivalent:

(i) $S$ is well-ordered;

(ii) $S$ is not dense;

(iii) $S$ is cyclic.

Let $\alpha$ be a non-zero real number and take $S=\langle 1,\alpha\rangle$ to be the subgroup of $(\mathbb R,+)$ generated by $1$ and $\alpha$. This is a cyclic group if and only if $\exists \beta, \langle 1,\alpha\rangle=\langle \beta\rangle$
$\Leftrightarrow 1=m\beta', \alpha=n\beta'$ for some $m,n\in\mathbb Z$ and $\beta'$
$\Leftrightarrow \alpha/1=n/m$, i.e. $\alpha$ is rational.

Now by the above corollary, $S$ is dense iff it is not well-ordered, i.e. iff

$(*)\qquad\forall\varepsilon>0,\exists m,n\in\mathbb Z, 0.

So we have the following criterion for irrationality:

Criterion 1. $\alpha$ is irrational if and only if $(*)$ holds.

Note that $S$ is dense in $\mathbb R$ iff $S/\mathbb Z=\{\{n\alpha\}:=n\alpha-\lfloor n\alpha\rfloor : n\in\mathbb Z\}$ is dense in $(0,1)$. So we deduce:

Criterion 2. $\alpha$ is irrational $\Leftrightarrow\forall\varepsilon>0,\exists n\in\mathbb Z, 0<\{n\alpha\}<\varepsilon$.

We demonstrate how this may be useful by proving that certain types of numbers are irrational.

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.

Proof. We have

$\displaystyle \left\{a_1\cdots a_nS\right\}=\left\{\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\right\}$.

Multiplying by $-1$ if necessary, we can take the expression in brackets on the right to be positive and it tends to $0$ as $n\to \infty$. Moreover, if

$\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=0$

then

$\displaystyle\frac{1}{a_{n+2}}+\frac{1}{a_{n+2}a_{n+3}}+\frac{1}{a_{n+2}a_{n+3}a_{n+4}}\dots=-1$

which cannot happen infinitely often as the left hand side tends to zero. So the conclusion follows by Criterion 2. $\square$

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.

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

Convergence follows easily from the ratio test, so $(\dagger)$ holds. Now

$\displaystyle\left|\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\right|$

$\displaystyle\le\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$

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

$\displaystyle =\frac{1}{|a_{n+1}|-1}\to 0$ as $n\to \infty$,

i.e. $(\ddagger)$ holds. $\square$

Some special cases of Proposition 2 are particularly interesting:

Corollary 1. $\displaystyle \sum_{n=0}^\infty\frac{1}{(n!)^k}$ is irrational for all positive integers $k$.

Proof. Take $a_n=n^k$. $\square$.

Corollary 2. $e$ is irrational.

Proof. Take $k=1$ in Corollary 1. $\square$

Corollary 3. $\sin 1$ and $\cos 1$ are irrational.

Proof. Take $a_1=1$ and for $n>1$, $a_n=-(2n-2)(2n-1)$ for sine, $a_n=-(2n-3)(2n-2)$ for cosine. $\square$

Corollary 4. $I_0(2)$ and $I_1(2)$ are irrational, where $I_\alpha(x)$ is the modified Bessel function of the first kind.

Proof. Taking $k=2$ in Corollary 1 shows that $I_0(2)$ is irrational. Taking $a_n=n(n+1)$ shows that $I_1(2)$ is irrational. $\square$

Corollary 5. $e^{\sqrt{2}}$ is irrational.

Proof. If it is rational, then so is $e^{-\sqrt{2}}$, and so is

$\displaystyle \cosh(\sqrt 2)=\frac{e^{\sqrt{2}}+e^{-\sqrt 2}}{2}=\sum_{n=0}^\infty\frac{2^n}{(2n)!}$.

Taking $a_n=n(2n-1)$ in the above shows that this is false. $\square$

Corollary 6. Let $k>1$ be an integer and $F_0,F_1,F_2,\dots$ the Fibonacci sequence. Then

(i) $\displaystyle \sum_{n=0}^\infty\frac{1}{k^{F_n}}$ is irrational.

(ii) $\displaystyle \sum_{n=0}^\infty\frac{1}{F_{k^n}}$ is irrational.

Proof. (i) Take $a_n=k^{F_n}$ and use $F_0+F_1+\dots+F_n=F_{n+2}-1$.

(ii) Take $a_n=F_{k^n}/F_{k^{n-1}}$. $\square$

1 Comment

Filed under Analysis, Number Theory