MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 edited body

Sorry, I couldn't get access to the paper you referred to. For a prime modulus $p>5$ it is easy to show that the period of the Fibonacci sequence is a factor of either $p-1$ or $2(p+1)$ depending on whether $5$ is a quadratic residue modulo $p$ or not (or by reciprocity, whether $5\equiv\pm1\pmod5$ p\equiv\pm1\pmod5$or not). This is because the roots of $$x^2-x-1=0$$ over$F_p$are either in$F_p^*$(if that polynomial factors modulo$p$), or in$F_{p^2}^*$. In the former case they are roots of unity of order that is a factor of$p-1$. And in the latter case the roots$\tau_1,\tau_2$are conjugates of each other, and hence satisfy both equations $$\tau_1^p=\tau_2,\qquad \tau_1\tau_2=-1$$ implying that they both are roots of unity of order dividing$2(p+1)$. The periodicity then follows from Binet's formula. Oh. Your program is leaving the integer domain. Are you sure you are not getting any overflows/loss of accuracy? You would need accuracy of something like 20 significant digits to handle$F_{200}$. Why aren't you using the recursive code? Storing two last entries is enough! 2 added 84 characters in body Sorry, I couldn't get access to the paper you referred to. For a prime modulus$p>5$it is easy to show that the period of the Fibonacci sequence is a factor of either$p-1$or$2(p+1)$depending on whether$5$is a quadratic residue modulo$p$or not (or by reciprocity: if , whether$5\equiv\pm1\pmod5$or not). This is because the roots of $$x^2-x-1=0$$ over$F_p$are either in$F_p^*$(if that polynomial factors modulo$p$), or in$F_{p^2}^*$. In the former case they are roots of unity of order that is a factor of$p-1$. And in the latter case the roots$\tau_1,\tau_2$are conjugates of each other, and hence satisfy both equations $$\tau_1^p=\tau_2,\qquad \tau_1\tau_2=-1$$ implying that they both are roots of unity of order dividing$2(p+1)$. The periodicity then follows from Binet's formula. Oh. Your program is leaving the integer domain. Are you sure you are not getting any overflows/loss of accuracy? You would need accuracy of something like 20 significant digits to handle$F_{200}$. Why aren't you using the recursive code? Storing two last entries is enough! 1 Sorry, I couldn't get access to the paper you referred to. For a prime modulus$p>5$it is easy to show that the period of the Fibonacci sequence is a factor of either$p-1$or$2(p+1)$depending on whether$5$is a quadratic residue modulo$p$or not (or by reciprocity: if$5\equiv\pm1\pmod5$or not). This is because the roots of $$x^2-x-1=0$$ over$F_p$are either in$F_p^*$(if that polynomial factors modulo$p$), or in$F_{p^2}^*$. And in the latter case the roots$\tau_1,\tau_2$are conjugates of each other, and hence satisfy both equations $$\tau_1^p=\tau_2,\qquad \tau_1\tau_2=-1$$ implying that they both are roots of unity of order dividing$2(p+1)$. The periodicity then follows from Binet's formula. Oh. Your program is leaving the integer domain. Are you sure you are not getting any overflows/loss of accuracy? You would need accuracy of something like 20 significant digits to handle$F_{200}\$. Why aren't you using the recursive code? Storing two last entries is enough!