The relation used by Matijasevich (alluded in the above entry of N. Takenov) is the following:
If $F_{n}^{2}|F_{m}$ then $F_{n}|m$ ...... (*)
In the 1992 Fall issue of the Intelligencer there is a contribution by Matijasevich where he mentioned the importance of such a result on his work concerning Hilbert's tenth problem. Here you have some of his thoughts:
"It is not difficult to prove this remarkable property of Fibonacci numbers after it has been stated, but it seems that this beautiful fact was not discovered until 1969. My original proof of () was based on a theorem proved by the Soviet mathematician N. Vorobyev in 1942 but published only in the third argumented (sic) edition of his popular book on the Fibonacci sequence... I studied the new edition of Vorobyev book in the summer of 1969 and that theorem attracted my attention at once. I did not deduce () at that time, but after I read Julia Robinson's paper I immediately saw that Vorobyev's theorem could be very useful. Julia Robinson did not see the third edition of Vorobyev's book until she received a copy from me in 1970. Who can tell what would have happened if Vorobyev had included his theorem in the first edition of his book? Perhaps, Hilbert's tenth problem would have been unsolved a decade earlier!"