Track / Stage 4 / 163 of 340 #1063 of 2604

Problem 1063

AMC 12 late, AIME early

Number theory Difficulty 4.7 Prove it India competition problems · India

Let $m$ and $n$ be two integers and define $a_0 = m$ , $a_1 = n$ and $a_{k+1} = 4a_k - 5a_{k-1}$ for $k \ge 1$ . If $p > 5$ is a prime such that $p-1$ is divisible by $4$ , then show that there are integers $m$ and $n$ such that $p$ does not divide $a_k$ for any $k \ge 0$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $t$ be an integer such that $p$ divides $t^2 + 1$ . There exists such an integer since $p-1$ is divisible by $4$ . Let $m = 1$ and $n = t + 2$ . Then
$n^2 = t^2 + 4t + 4 \equiv 4t + 3 \equiv 4n - 5m \pmod{p}.$
Therefore, if $a_0 = 1$ and $a_1 = n$ then $a_2 \equiv n^2 \pmod{p}$ . By induction, it is easy to see that $a_k \equiv n_k \pmod{p}$ . Since $p > 5$ , it follows that $p$ does not divide $n$ . Therefore $p$ does not divide $a_k$ for any $k \ge 0$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.