Track / Stage 4 / 326 of 340 #1066 of 2444

Problem 1066

AMC 12 late, AIME early

Algebra Difficulty 5.0 Prove it Turkish Mathematical Olympiad · Turkey

Let $a_{n+1} = a_n^3 - 2a_n^2 + 2$ for all $n \ge 1$ and $a_1 = 5$ . Prove that if $p \equiv 3 \pmod 4$ is a prime divisor of $a_{2011} + 1$ , then $p = 3$ .

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

Observe that $a_{n+1} - 2 = a_n^2(a_n - 2)$ for all $n \ge 1$ . By induction on $n$ we obtain $a_{n+1} - 2 = 3a_n^2a_{n-1}^2 \cdots a_1^2$ for all $n \ge 1$ . Therefore $a_{2011} + 1 = 3(a_{2010}^2a_{2009}^2 \cdots a_1^2 + 1) = (a_{2010}a_{2009} \cdots a_1)^2 + 1$ .

Let $p \equiv 3 \pmod 4$ be a prime divisor of $a_{2011} + 1$ . It is well known that if $q$ is a prime divisor of $(a_{2010}a_{2009} \cdots a_1)^2 + 1$ , then $q \equiv 1 \pmod 4$ or $q = 2$ . Thus $p|3$ . That is $p = 3$ .

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