Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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 – 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.


share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.