Competition problem — Number theory

Number theory Difficulty 4.7 AIME Prove it 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$ .

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$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.