# Primitive squareful Fibonacci numbers

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.

-
Perhaps there is a theorem that says that if a prime $p$ divides $F_k$ then $p^2$ divides $F_{pk}$. –  Gerry Myerson Oct 23 '12 at 0:45

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.

-
How do you calculate the value of $F_{-i}$ with -i negative? –  wnvl Oct 23 '12 at 13:32
OK, it is explained in the wiki page F_{-i}=-(-1)^iF_i –  wnvl Oct 23 '12 at 14:18
Apparently there is a difference between squareful and squarefull. 12 is squareful oeis.org/wiki/Squareful_numbers –  wnvl Oct 23 '12 at 14:25
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}$. –  Gerry Myerson Oct 23 '12 at 21:29

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

-
Please don't place unrelated self-promoting links into answers. There's space on your user page where you can put such things. –  joriki Oct 23 '12 at 15:08
ok, will do that. I will discontinue it from now. Removing URL now. –  Salahuddin Oct 23 '12 at 15:49