Vorobiev's Theorem

Vorobiev's theorem states that if , then , where  is a Fibonacci number and  means  divides . The theorem was discovered by Vorobiev in 1942, but not published until 1967. It was used by Y. Matiyasevich in his negative solution to the Hilbert's tenth problem.

Note that the converse does not hold. For example, , but . The plot above shows values of  for which  and  (black) and for which  but  (red).

REFERENCES:

Vorobiev, N. N. Fibonacci Numbers. Basel, Switzerland: Birkhäuser, 2002.