For a prime power q and an elliptic curve E over F_q having q+1-a points, where a ∈ [-2√q,2√q], let #E_m, m ≥ 1, be the sequence of numbers whose mth term is the number of points of E over F_q^m. In this paper, we determine all instances when #({#E_m}∩{F_n})≥ 2, where {F_n} (n≥1) is the sequence of Fibonacci numbers. That is, we determine all six--tuples (a,q,m₁,m₂,n₁,n₂) such that #E=q+1-a, #E_m1=F_n1 and #E_m2=F_n2.

The authors thank the Department of Mathematics at the Universidad del Valle for the Cluster time used to perform calculations, and especially the Computer Center Jurgen Tischer for their advice on parallelisation of the algorithm used. Yu. B. worked on this paper when he was visiting Universidad de Valparaíso, supported by the Project MEC 80160038, and Institute of Mathematical Sciences in Chennai, supported by SPARC Project P445. He thanks Instituto de Matemáticas UV and IMSc for excellent working conditions. C.A.G. was supported in part by Project 71228 (Universidad del Valle). J.C.G. worked on this project during a visit to the FLAME in Morelia, Mexico, in August 2019. This author also thanks the Universidad del Valle for support during his Ph.D. studies. F.L worked on this paper while he was visiting the Max Planck Institute for Mathematics in Fall 2019. He thanks this institution for hospitality and support. In addition, F. L. was also supported in part by grant CPRR160325161141 from the NRF of South Africa and the Focus Area Number Theory grant RTNUM19 from CoEMaSS Wits.

The authors thank Karim Belabas, Yann Bugeaud and Amalia Pizarro-Madariaga for stimulating discussions and helpful suggestions, and the referee for careful reading of the manuscript and useful comments.