Monthly Archives: August 2015

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++) {
    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) {
    unsigned long long Fp, P, Q;
    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;
    printf("Fibonacci(%d)=%llu is prime.", p, Fp);
    return 0;


Filed under Number Theory

Another Inequality Involving Sigma and Tau

cf. An Inequality Involving Sigma and Tau.

Let n be a positive integer. By the weighted AM-GM inequality, one has

\displaystyle\frac{\sum d\cdot n/d}{\sum n/d}\ge\left(\prod d^{n/d}\right)^\frac{1}{\sum n/d},

where all sums and products are taken over the positive divisors d of n. This means

\displaystyle\boxed{\frac{n\tau(n)}{\sigma(n)}\ge\left(\prod_{d\mid n}d^{1/d}\right)^{n/\sigma(n)}}.

Considering the analytic behaviour of the function f(x)=x^{1/x} one deduces

\displaystyle\prod_{d\mid n}d^{1/d}\ge\prod_{1\neq d\mid n}n^{1/n}=n^{(\tau(n)-1)/n}

for any n, with equality iff n is prime or 1 or 4. (By convention we take an empty product to be 1.) Combining this with the first inequality in this post we obtain

\displaystyle n^{1/2}\ge\frac{n\tau(n)}{\sigma(n)}\ge n^\frac{\tau(n)-1}{\sigma(n)},


\boxed{\displaystyle n^{1/2}\le\frac{\sigma(n)}{\tau(n)}\le n^{1-\frac{\tau(n)-1}{\sigma(n)}}}.

This strengthens the first boxed inequality from this post.

Leave a comment

Filed under Number Theory