Problem 1512

Solution:

Let $x + \frac{1}{x} = 3$.

Let $a_n = x^n + \frac{1}{x^n}$ for $n \geq 0$.

We have the recurrence:
$$a_{n} = (x^n + x^{-n}) = (x + x^{-1}) a_{n-1} - a_{n-2}$$
So,
$$a_n = 3 a_{n-1} - a_{n-2}$$
with $a_0 = 2$, $a_1 = 3$.

Let us compute $a_2$:
$$a_2 = 3 a_1 - a_0 = 3 \times 3 - 2 = 7$$
$a_3 = 3 a_2 - a_1 = 3 \times 7 - 3 = 18$.
$a_4 = 3 a_3 - a_2 = 3 \times 18 - 7 = 47$.

But we need $a_{2^{2013}}$ modulo $100$ (the last two digits).

Let us look for a pattern modulo $100$.

Compute a few terms modulo $100$:
$a_0 = 2$
$a_1 = 3$
$a_2 = 7$
$a_3 = 18$
$a_4 = 47$
$a_5 = 94$
$a_6 = 35$
$a_7 = 11$
$a_8 = 68$
$a_9 = 95$
$a_{10} = 79$
$a_{11} = 42$
$a_{12} = 47$
$a_{13} = 83$
$a_{14} = 44$
$a_{15} = 5$
$a_{16} = 10$
$a_{17} = 25$
$a_{18} = 65$
$a_{19} = 20$
$a_{20} = 95$

Let us try to find the period. Compute $a_{22}$:
$a_{21} = 3 \times 95 - 20 = 285 - 20 = 265 \equiv 65 \pmod{100}$
$a_{22} = 3 \times 65 - 95 = 195 - 95 = 100 \equiv 0 \pmod{100}$
$a_{23} = 3 \times 0 - 65 = -65 \equiv 35 \pmod{100}$
$a_{24} = 3 \times 35 - 0 = 105 - 0 = 105 \equiv 5 \pmod{100}$
$a_{25} = 3 \times 5 - 35 = 15 - 35 = -20 \equiv 80 \pmod{100}$
$a_{26} = 3 \times 80 - 5 = 240 - 5 = 235 \equiv 35 \pmod{100}$
$a_{27} = 3 \times 35 - 80 = 105 - 80 = 25 \pmod{100}$
$a_{28} = 3 \times 25 - 35 = 75 - 35 = 40 \pmod{100}$
$a_{29} = 3 \times 40 - 25 = 120 - 25 = 95 \pmod{100}$
$a_{30} = 3 \times 95 - 40 = 285 - 40 = 245 \equiv 45 \pmod{100}$

Alternatively, let's try to find the period for $a_n$ modulo $100$.

Alternatively, note that $x + \frac{1}{x} = 3$.
The minimal polynomial is $x^2 - 3x + 1 = 0$.
The roots are $x = \frac{3 \pm \sqrt{5}}{2}$.
Let $\alpha = \frac{3 + \sqrt{5}}{2}$, $\beta = \frac{3 - \sqrt{5}}{2}$.

Then $a_n = \alpha^n + \beta^n$.

We are to compute $a_{2^{2013}} \bmod 100$.

Note that $\alpha \beta = 1$.

Also, $a_n$ satisfies the recurrence $a_n = 3 a_{n-1} - a_{n-2}$.

Let us try to find the period of $a_n$ modulo $100$.

Alternatively, note that $a_n$ modulo $100$ is periodic, and the period divides $10000$ (since the recurrence is order 2, modulo $m$, the period divides $m^2 - 1$).

Alternatively, let's compute $a_n$ modulo $4$ and $25$ separately, then use the Chinese Remainder Theorem.

First, modulo $4$:
$a_0 = 2$
$a_1 = 3$
$a_2 = 3 \times 3 - 2 = 9 - 2 = 7 \equiv 3 \pmod{4}$
$a_3 = 3 \times 3 - 3 = 9 - 3 = 6 \equiv 2 \pmod{4}$
$a_4 = 3 \times 2 - 3 = 6 - 3 = 3 \pmod{4}$
$a_5 = 3 \times 3 - 2 = 9 - 2 = 7 \equiv 3 \pmod{4}$
$a_6 = 3 \times 3 - 3 = 9 - 3 = 6 \equiv 2 \pmod{4}$
So the sequence modulo $4$ is: $2, 3, 3, 2, 3, 3, 2, 3, 3, 2, \ldots$
It repeats every 3 terms after the first.

Let's check:
$a_0 = 2$
$a_1 = 3$
$a_2 = 3$
$a_3 = 2$
$a_4 = 3$
$a_5 = 3$
$a_6 = 2$
$a_7 = 3$
$a_8 = 3$
$a_9 = 2$
So the period is 3, starting from $a_1$.

So for $n \geq 1$, $a_n$ modulo $4$ cycles as $3, 3, 2$.

Now, $2^{2013}$ modulo $3$:
$2^1 \equiv 2 \pmod{3}$
$2^2 \equiv 1 \pmod{3}$
$2^3 \equiv 2 \pmod{3}$
$2^4 \equiv 1 \pmod{3}$
So $2^k$ cycles $2, 1, 2, 1, \ldots$
$2013$ is odd, so $2^{2013} \equiv 2 \pmod{3}$.

So $a_{2^{2013}}$ modulo $4$:
If $n \equiv 1 \pmod{3}$, $a_n \equiv 3$
If $n \equiv 2 \pmod{3}$, $a_n \equiv 3$
If $n \equiv 0 \pmod{3}$, $a_n \equiv 2$

$2^{2013} \equiv 2 \pmod{3}$, so $a_{2^{2013}} \equiv 3 \pmod{4}$.

Now, modulo $25$:
$a_0 = 2$
$a_1 = 3$
$a_2 = 3 \times 3 - 2 = 9 - 2 = 7$
$a_3 = 3 \times 7 - 3 = 21 - 3 = 18$
$a_4 = 3 \times 18 - 7 = 54 - 7 = 47 \equiv 22 \pmod{25}$
$a_5 = 3 \times 22 - 18 = 66 - 18 = 48 \equiv 23 \pmod{25}$
$a_6 = 3 \times 23 - 22 = 69 - 22 = 47 \equiv 22 \pmod{25}$
$a_7 = 3 \times 22 - 23 = 66 - 23 = 43 \equiv 18 \pmod{25}$
$a_8 = 3 \times 18 - 22 = 54 - 22 = 32 \equiv 7 \pmod{25}$
$a_9 = 3 \times 7 - 18 = 21 - 18 = 3 \pmod{25}$
$a_{10} = 3 \times 3 - 7 = 9 - 7 = 2 \pmod{25}$
$a_{11} = 3 \times 2 - 3 = 6 - 3 = 3 \pmod{25}$
$a_{12} = 3 \times 3 - 2 = 9 - 2 = 7 \pmod{25}$
So the sequence is:
$2, 3, 7, 18, 22, 23, 22, 18, 7, 3, 2, 3, 7, \ldots$

It appears to repeat every 10 terms:
$a_{10} = 2$, $a_{11} = 3$, $a_{12} = 7$, which matches $a_0, a_1, a_2$.
So period is 10.

Now, $2^{2013}$ modulo $10$:
$2^1 = 2$
$2^2 = 4$
$2^3 = 8$
$2^4 = 16 \equiv 6$
$2^5 = 32 \equiv 2$
$2^6 = 64 \equiv 4$
$2^7 = 128 \equiv 8$
$2^8 = 256 \equiv 6$
So the cycle is $2, 4, 8, 6$ (period 4).

$2013 \div 4 = 503$ remainder $1$, so $2^{2013} \equiv 2$ (since $2^{4k+1} \equiv 2$).

So $n = 2$ modulo $10$.
So $a_{2^{2013}} \equiv a_2 \equiv 7 \pmod{25}$.

Now, combine $a_{2^{2013}} \equiv 3 \pmod{4}$ and $a_{2^{2013}} \equiv 7 \pmod{25}$.

Let $x \equiv 3 \pmod{4}$, $x \equiv 7 \pmod{25}$.

Let $x = 25k + 7$.
$25k + 7 \equiv 3 \pmod{4}$
$25 \equiv 1 \pmod{4}$, so $k + 7 \equiv 3 \pmod{4}$
$k \equiv 3 - 7 \equiv -4 \equiv 0 \pmod{4}$
So $k = 4m$, $x = 25 \times 4m + 7 = 100m + 7$
So the last two digits are $07$.

Therefore, the answer is $\boxed{07}$.