Prove that there is no positive integer $n$ for which $n^7-77$ is a Fibonnaci number.

Question

The author in the solution hints towards using $\pmod {29}$ which I don't understand to use anyhow.

Answer 1

The Fibonacci numbers $x_n$ arise by iterating $$\begin{pmatrix} x_{n+1} \\ x_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_n \\ x_{n-1} \end{pmatrix}.$$ With the fact that $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{14} = \begin{pmatrix} 610 & 377 \\ 377 & 233 \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \; \bmod 29,$$ we see that the remainders of Fibonacci numbers modulo $29$ repeat with period $14$: $$0,1,1,2,3,5,8,13,21,5,26,2,28,1,...$$ and in particular, the only remainders of Fibonacci numbers modulo $29$ are $0,1,2,3,5,8,13,21,26,28.$

The only seventh powers modulo $29$ are $0,\pm 1$ and $\pm 12$ (using the fact that $((\mathbb{Z}/29\mathbb{Z})^{\times})^7 \cong 7 \mathbb{Z}/28 \mathbb{Z} \cong \mathbb{Z}/4\mathbb{Z}.$) Subtracting $77$ mod $29$ (i.e. adding $10$) to any of these five numbers does not result in the remainder of a Fibonacci number.