Tag Archives: fibonacci number

Factoring Fibonacci numbers

I just wrote a C program based off 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 code some years back 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.

#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;
    }
    if (Q*Q>Fp) printf("Fibonacci(%d)=%llu is prime.", p, Fp);
    return 0;
}
Advertisements

2 Comments

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<s_0<s_1<\cdots 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.

Leave a comment

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

2 Comments

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<m\alpha-n<\varepsilon.

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