Competition problem — Number theory

Library / /343 of 348

Number theory Difficulty 5.3 AIME, harder Find the answer

Let a sequence $\left\{a_{n}\right\}_{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$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

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 1 cm 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(\bmod 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.