# Monthly Archives: August 2015

## 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;
}

Filed under Number theory

## Another 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)}$,

i.e.,

$\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.