How find the sum of the last two digits of $(x^{2})^{2013} + \frac{1}{(x^{2})^{2013}}$ for $x + \frac{1}{x} = 3$? Let x be a real number so that $x + \frac{1}{x} = 3$. How find the sum of the last two digits of $(x^{2})^{2013} + \frac{1}{(x^{2})^{2013}}$?
 A: I haven't solved this yet but my approach so far is along the lines of:
$$\begin{align}
x+\frac{1}{x}&=3\\
\therefore \left(x+\frac{1}{x}\right)^2&=3^2\\
\therefore x^2+\frac{1}{x^2}+2&=9\implies x^2+\frac{1}{x^2}=7
\end{align}$$
Now we make use of this result and notice the following pattern:
$$\begin{align}
x^2+\frac{1}{x^2}&=7\\
x^4+\frac{1}{x^4}&=\left(x^2+\frac{1}{x^2}\right)\left(x^2+\frac{1}{x^2}\right)-2&&=7\left(x^2+\frac{1}{x^2}\right)-2\\
x^6+\frac{1}{x^6}&=\left(x^2+\frac{1}{x^2}\right)\left(x^4+\frac{1}{x^4}\right)-\left(x^2+\frac{1}{x^2}\right)&&=7\left(x^4+\frac{1}{x^4}\right)-\left(x^2+\frac{1}{x^2}\right)\\
x^8+\frac{1}{x^8}&=\left(x^2+\frac{1}{x^2}\right)\left(x^6+\frac{1}{x^6}\right)-\left(x^4+\frac{1}{x^4}\right)&&=7\left(x^6+\frac{1}{x^6}\right)-\left(x^4+\frac{1}{x^4}\right)\\
&\cdots\\
x^{2n}+\frac{1}{x^{2n}}&=\left(x^2+\frac{1}{x^2}\right)\left(x^{2(n-1)}+\frac{1}{x^{2(n-1)}}\right)-\left(x^{2(n-2)}+\frac{1}{x^{2(n-2)}}\right)&&=7\left(x^{2(n-1)}+\frac{1}{x^{2(n-1)}}\right)-\left(x^{2(n-2)}+\frac{1}{x^{2(n-2)}}\right)\\
\end{align}$$
If we now let:$$a_n=x^{2n}+\frac{1}{x^{2n}}$$then this can be written as the following recurrence relation:$$a_n=7a_{n-1}-a_{n-2}$$which can be solved to yield:$$a_n=x^{2n}+\frac{1}{x^{2n}}=\left(\frac{7+3\sqrt{5}}{2}\right)^{n}+\left(\frac{7-3\sqrt{5}}{2}\right)^{n}, n=0,1,2,3,\cdots$$
We now need to compute the sum of last two digits for $n=2013$
A: Recall that a linear recurrence sequence (with constant coefficients) is a sequence $U = \{u_n\}_{n=0}^{\infty}$ with terms in $\Bbb{C}$ such that
$$
u_n = c_1 u_{n-1} + \dotsc + c_m u_{n-m} \quad \text{for all } n \geq m \tag{1} \label{eq:1}
$$
where $c_1,\dotsc,c_m$ are complex constants with $c_m \neq 0$. The numbers $u_0,\dotsc,u_{m-1}$ are called the initial values of $U$.
Now, while $U$ may satisfy various relations of type $\eqref{eq:1}$, it can be shown that there is a unique relation of minimal length $k$, the order of $U$. The polynomial
$$
f_U(X) = X^k - c_1 X^{k-1} - \dotsc - c_k
$$
is the companion polynomial of $U$, and its study leads to a very interesting result:

Theorem: Let $\lambda_1,\dotsc,\lambda_h$ be the distinct (complex) roots of $f_U$, with multiplicities $e_1,\dotsc,e_h$ respectively. Then there are polynomials $g_1,\dotsc,g_h \in \Bbb{C}[X]$ with $\deg g_i \leq e_i$ such that
  $$
u_n = g_1(n) \lambda_1^n + \dotsc + g_h(n) \lambda_h^n \quad \text{for all } h \geq 0. \tag{2} \label{eq:2}
$$
  Conversely, every sequence satisfying $\eqref{eq:2}$ is a linear recurrence sequence.
Proof: Cfr. Theorem 9.10 from these notes.


Why did I bring this up? Well... since $x + \frac{1}{x} = 3$, we know that $x$ is a root of the polynomial $X^2 - 3X + 1$, thus $x$ is either
$$
\lambda_1 := \frac{3 + \sqrt{5}}{2} \quad \text{or} \quad \lambda_2 := \frac{3 - \sqrt{5}}{2}.
$$
Interestingly, these are the inverse of each other, thus
$$
x^n + \frac{1}{x^n} = \lambda_1^n + \lambda_2^n =: u_n.
$$
Thus $\{u_n\}_{n=0}^\infty$ is the linear recurrence sequence defined by the relation
$$
u_n = 3 u_{n-1} - u_{n-2}
$$
with initial data $u_0 = \lambda_1^0 + \lambda_2^0 = 2$ and $u_1 = \lambda_1 + \lambda_2 = 3$.
This leads to a simple recursive algorithm to compute (exactly) the last two digits of any $u_n$, and doing this modulo $100$ is very fast even for large $n$. Here's a naive way to compute $u_{2 \cdot 2013} \pmod{100}$ in Mathematica:
rec[n_Integer] := LinearRecurrence[{3, -1}, {3, 7}, {n, n}] // First;
Mod[rec[2*2013], 100]
(* 22 *)

Also, if you don't trust what I wrote above, you can easily test that this recurrence does indeed give the numbers we want:
AllTrue[Range[100], rec[#] == N[((3 - Sqrt[5])/2)^# + ((3 + Sqrt[5])/2)^#] &]
(* True *)

A: Square your equation to get:
$$x^2+\frac{1}{x^2}=3^2 - 2$$
And again:
$$x^4+\frac{1}{x^4}=(3^2 - 2)^2-2$$
So:
$$x^{2^n}+\frac{1}{x^{2^n}}=(\ldots((3^2 - 2)^2-2)^2 -2)\ldots)^2 -2$$
Define:
$$a_{n+1} = a_n^2 - 2$$
Now let $a_n = 100 b_n + y_n$. So that:$$a_{n+1} = 100^2 +200 b_n y_n+ y_n^2 - 2$$
$$y_{n+1} = y_n^2 - 2\mod 100$$
Start with $y_1=7$. $y_2 = 47$ and $y_3 = 107 \equiv 7$.
Edit:
This works to get us a answer if we had $2048$ instead of $2013$. 
Working on an alternate solution.
