HMMT-Feb 2017 alg, Problem 9

The Fibonacci sequence is defined as follows: $F_{0}=0, F_{1}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ for all integers $n \geq 2$. Find the smallest positive integer $m$ such that $F_{m} \equiv 0(\bmod 127)$ and $F_{m+1} \equiv 1(\bmod 127)$.

Solution: First, note that 5 is not a quadratic residue modulo 127. We are looking for the period of the Fibonacci numbers mod 127. Let $p=127$. We work in $\mathbb{F}_{p^{2}}$ for the remainder of this proof. Let $\alpha$ and $\beta$ be the roots of $x^{2}-x-1$. Then we know that $F_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}$. Note that since $x \rightarrow x^{p}$ is an automorphism and since automorphisms cycle the roots of a polynomial we have that $\alpha^{p}=\beta$ and $\beta^{p}=\alpha$. Then $F_{p}=\frac{\alpha^{p}-\beta^{p}}{\alpha-\beta}=-1$ and $F_{p+1}=\frac{\alpha \beta-\beta \alpha}{\alpha-\beta}=0$ and similarly we obtain $F_{2 p+1}=1$ and $F_{2 p+2}=0$. Thus since $2 p+2$ is a power of 2 and since the period does not divide $p+1$, we must have the answer is $2 p+2=256$. $\fbox{256}$.

Answer: 256