fibonacci series mod a number - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:35:55Z http://mathoverflow.net/feeds/question/40816 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40816/fibonacci-series-mod-a-number fibonacci series mod a number unknown (google) 2010-10-02T05:18:35Z 2010-11-07T17:19:14Z <p>I'm trying to write a program with an input of numbers $n$ and $k$ (where $n&lt;10^{1000}$ and $k&lt;10^9$), where I compute fib[n] % k. What is a good FAST way of computing this? </p> <p>I realize that the resulting series is periodic, just not sure how to find it efficiently.</p> http://mathoverflow.net/questions/40816/fibonacci-series-mod-a-number/40818#40818 Answer by Robin Chapman for fibonacci series mod a number Robin Chapman 2010-10-02T06:51:18Z 2010-10-02T06:51:18Z <p>This is really just an expansion of Gerhard's comment. One has the matrix formula $$\begin{pmatrix} 1&amp;1\\ 1&amp;0 \end{pmatrix}^n= \begin{pmatrix} F_{n+1}&amp;F_n\\ F_n&amp;F_{n-1} \end{pmatrix}$$ so the problem reduces to computing $A^n$ modulo $k$ where $$A=\begin{pmatrix} 1&amp;1\\ 1&amp;0 \end{pmatrix}.$$ This can be done by the <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow">repeated squaring</a> method often used in <a href="http://en.wikipedia.org/wiki/Modular_exponentiation" rel="nofollow">modular exponentiation</a>. The idea is to compute $A^n$ recursively either as $(A^m)^2$ or $A(A^m)^2$ according to whether $n=2m$ or $n=2m+1$.</p> http://mathoverflow.net/questions/40816/fibonacci-series-mod-a-number/45183#45183 Answer by Andreas Rüdinger for fibonacci series mod a number Andreas Rüdinger 2010-11-07T17:19:14Z 2010-11-07T17:19:14Z <p>Perhaps Elsenhans, Jahnel, "The Fibonacci sequence modulo $p^2$ – An investigation by computer for $p &lt; 10^{14}$" <a href="http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf" rel="nofollow">http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf</a> will be interesting for you. There are sections about the algorithm. </p>