1
$\begingroup$

In https://oeis.org/A065069 numbers $n$ such that Fibonacci($n$) is not squarefree, but for all proper divisors $k$ of $n$, Fibonacci($k$) is squarefree, are listed.

OEIS gives a Mathematica program (see link) to calculate these indices. The algorithm used, searches primes $p$ and Fibonacci numbers Fib($k$) such that

$\text{Fib}(k)\;\text{mod}\,p =0$

The numbers $p\cdot k$ are candidates to be indices of primitive squareful Fibonacci numbers.

Can anyone explain me the reasonning behind this algorithm? Probably some theorems about Fibonacci numbers I don't know are used.

I am interested in alternative algorithms as well.

  • 0
    Perhaps there is a theorem that says that if a prime $p$ divides $F_k$ then $p^2$ divides $F_{pk}$.2012-10-23

2 Answers 2

2

The Wikipedia article on Fibonacci numbers says $F_{kn+c}=\sum_0^k{k\choose i}F_{c-i}F_n^iF_{n+1}^{k-i}$ Let $c=0$, and let $k=p$ be prime, so $F_{pn}=pF_{-1}F_nF_{n+1}^{p-1}+\sum_2^p{p\choose i}F_{-i}F_n^iF_{n+1}^{p-i}$ Note that the $i=0$ term vanishes because $F_0=0$, and I have separated out the $i=1$ term. If $p\mid F_n$, then $p^2$ divides every term on the right side, so $p^2\mid F_{pn}$.

It seems to me that the question is suggesting that squareful is the negation of squarefree, but this is not the case. E.g., the number $12$ is neither squareful nor squarefree.

  • 0
    I wasn't aware of that usage. With all due respect to whoever came up with it, I think it's a very bad coinage. As for negative subscripts, the basic recursion, $F_{n+1}=F_n+F_{n-1}$ can be made to run backwards, e.g., you can get $F_{-1}$ from $F_1=F_0+F_{-1}$.2012-10-23
2

okay, till $F_{3n}$, it seems true.

$F_{2n} = 2F_{n-1}F_{n} + F_{n}^{2}$, which is divisible by $2^2$.

$F_{3n} = 3F_{n-1}^{2}F_{n} + 3F_{n}^{2}F_{n-1} + 2F_{n}^{3}$ is also divisible by $3^2$.

There might be an inductive way of proving it.

Salahuddin

  • 1
    ok, will do that. I will discontinue it from now. Removing URL now.2012-10-23