Define a sequence $(x_{n})_{n\geq 1}$ by taking $x_{1}\in\left\{5,7\right\}$; when $k\ge 1$, $x_{k+1}\in\left\{5^{x_{k}},7^{x_{k}}\right\}$. Determine all possible last two digits of $x_{2009}$.
Problem
Source: 2009 China Western Mathematic Olmpiad
Tags: modular arithmetic, number theory proposed, number theory
dinoboy
25.02.2012 22:25
Another easy Chinese Olympiad? Notice if $x_{2009} = 5^{x_{2008}}$, then no matter what the last two ending digits are $25$. Now observe that $\text{ord}_{100}(7) = 4$. Hence if $x_{2009} = 7^{x_{2008}}$ we only care about $x_{2008} \pmod{4}$. If $x_{2008} = 5^{x_{2007}}$ then $x_{2008} \equiv 1 \pmod{4}$. If $x_{2008} = 7^{x_{2007}}$ then $x_{2008} \equiv 3 \pmod{4}$. Hence it immediately follows the only possible endings are $\boxed{25,07,43}$.
AlastorMoody
11.10.2019 14:57
China Western MO 2009 P5 wrote:
Define a sequence $(x_{n})_{n\geq 1}$ by taking $x_{1}\in\left\{5,7\right\}$; when $k\ge 1$, $x_{k+1}\in\left\{5^{x_{k}},7^{x_{k}}\right\}$. Determine all possible last two digits of $x_{2009}$.
Solution: Regardless of what $x_{2008}$ is, If $x_{2009}=5^{x_{2008}} \implies x_{2009} \equiv 25 \pmod{100}$. Suppose, if $x_{2009}$ $=$ $7^{x_{2008}}$. Now, if $x_{2008}=5^{x_{2007}}$ $\equiv$ $1$ $\pmod{4}$ $\implies$ $x_{2008}$ $\equiv$ $7 \pmod{100}$. If $x_{2008}$ $=$ $7^{x_{2007}}$ And Since, $x_{2007}$ is odd $\implies$ $x_{2009}$ $ \equiv$ $ 43 $ $\pmod{100}$, Hence, $07,25,43$ are the possible last two digits $\qquad \blacksquare$