Library / /661 of 740

, 2014

Algebra Difficulty 5.6 AIME, harder Prove it United States

Problem:

Let a sequence $\{a_{n}\}_{n=0}^{\infty}$ be defined by $a_{0}=\sqrt{2}$ , $a_{1}=2$ , and $a_{n+1}=a_{n} a_{n-1}^{2}$ for $n \geq 1$ . The sequence of remainders when $a_{0}, a_{1}, a_{2}, \cdots$ are divided by $2014$ is eventually periodic with some minimal period $p$ (meaning that $a_{m}=a_{m+p}$ for all sufficiently large integers $m$ , and $p$ is the smallest such positive integer). Find $p$ .

Solution

Solution:

Answer: $12$

Let $a_{n}=2^{b_{n}}$ , so notice $b_{1}=1$ , $b_{2}=2$ , and $b_{n+1}=b_{n}+2 b_{n-1}$ for $n \geq 1$ , so by inspection $b_{n}=2^{n-1}$ for all $n$ ; thus $a_{n}=2^{2^{n-1}}$ .

$2014 = 2 \cdot 19 \cdot 53$ so we just want to find the lcm of the eventual periods of $2^{n} \bmod \operatorname{ord}_{19}(2)$ and $\operatorname{ord}_{53}(2)$ . These orders divide $18$ and $52$ respectively, and we can manually check $\operatorname{ord}_{9}(2)=6$ and $\operatorname{ord}_{13}(2)=12$ . The lcm of these is $12$ , so to show the answer is $12$ , it suffices to show that $13 \mid \operatorname{ord}_{53}(2)$ . This is true since $2^{4} \not \equiv 1 \pmod{53}$ . So, the answer is $12$ .

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 reproduced verbatim; metadata (topic, difficulty) added by this project.