Evaluating $\lfloor (3 + \sqrt{5})^{34} \rfloor \pmod {100}$ The problem is to evaluate $\lfloor (3 + \sqrt{5})^{34} \rfloor \pmod {100}$
No calculators are allowed. 
I think I have to get rid of $\sqrt{5}$ somehow since it is irrational and would make it hard to find the floor without doing it numerically. But I'm not sure how.
 A: This answer inspired by the Fibonacci sequence, in that $$F_n = \frac{\varphi^n - \overline{\varphi}\,^n}{\sqrt 5} = \frac{\lfloor{\varphi^n}\rfloor + 1}{\sqrt 5} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n\,_{2,1}$$
which gives us an easy way to compute $\lfloor \varphi^n \rfloor$ using the above matrix.  So attempting to find a matrix that allows the computation of $\lfloor\phi^n\rfloor$ for $\phi = 3 + \sqrt 5$ and $\overline \phi = 3 - \sqrt 5$, consider the matrix:
$$M = \begin{bmatrix} A & B \\ C & D \end{bmatrix} \tag 1$$
It has characteristic equation 
$$P(x) = x^2 - (D+A)x + AD - BC \tag 2$$
which to have the desired eigenvalues, the characteristic equation must also be:
$$P(x) = (x - \phi)(x - \overline \phi) = x^2 - 6x + 4 \tag 3$$
Eliminating variables $C$ and $D$ between (1) (2) and (3), it leaves:
$$M = \begin{bmatrix} A & B \\ \frac{(6-A)A - 4}{B} & 6 - A \end{bmatrix} \tag 4$$
Now any choice of $A$ and $B$ will work, but to choose something easy, consider $A = 3$ to make the diagonal nice and $B=1$ to make the rest nice:
$$M = \begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix}$$
with the eigenvalue decomposition being:
$$M = 
\begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix}
\begin{bmatrix} 3 + \sqrt{5} & 1 \\ 0 & 3 - \sqrt{5}\end{bmatrix}
\begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix}^{-1}
$$
and it follows:
$$M^n =
\begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix}
\begin{bmatrix} \phi^n & 1 \\ 0 & \overline \phi\,^n\end{bmatrix}
\begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix}^{-1}
=
\begin{bmatrix}
   \frac{\phi^n + \overline \phi\,^n}{2} & \frac{\phi^n + \overline \phi\,^n}{2\sqrt{5}} \\
   \frac{\phi^n + \overline \phi\,^n}{2 / \sqrt{5}} & \frac{\phi^n + \overline \phi\,^n}{2} \\
\end{bmatrix}
$$
So we have $2 M^n\,_{1,1} = \phi^n + \overline \phi\,^n = \lfloor \phi^n \rfloor + 1$, altogether:
$$\lfloor(3 + \sqrt{5})^n\rfloor = 2 {\begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix}^n}_{1,1} - 1$$
$$\downarrow$$
$$\boxed{\lfloor(3 + \sqrt{5})^n\rfloor \equiv 2 {\begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix}^n}_{1,1} - 1 \pmod{100}} \tag{!!}$$
Matrix modular exponentiation with integers is fairly easy to do with repeated squaring:
$$
\begin{array} {|c|c|} \hline
M^1                  & \begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix} \\ \hline
M^2 = (M^1)^2        & \begin{bmatrix} 14 & 6 \\ 30 & 14 \end{bmatrix} \\ \hline
M^4 = (M^2)^2        & \begin{bmatrix} 76 & 68 \\ 40 & 76 \end{bmatrix} \\ \hline
M^8 = (M^4)^2        & \begin{bmatrix} 96 & 36 \\ 80 & 96 \end{bmatrix} \\ \hline
M^{16} = (M^8)^2       & \begin{bmatrix} 96 & 12 \\ 60 & 96 \end{bmatrix} \\ \hline
M^{32} = (M^{16})^2    & \begin{bmatrix} 36 & 4 \\ 30 & 36 \end{bmatrix} \\ \hline
M^{34} = M^{32}M^2     & \begin{bmatrix} 24 & 70 \\ 60 & 24 \end{bmatrix} \\ \hline
\end{array}$$
So $\lfloor(3 + \sqrt{5})^{34}\rfloor \equiv 2 \times 24 - 1 \equiv 47 \pmod{100}$

It seems that using the above style argument, one can say in general that if $0 < X - \sqrt{Y} < 1$, then the follow identity holds:
$$\lfloor (X + \sqrt{Y})^n \rfloor = 2{\begin{bmatrix} X & Y \\ 1 & X \end{bmatrix}^n}_{1,1} - 1$$
I wonder if this is a well known identity?
A: Hint: Add $(3 - \sqrt{5})^{34}$ inside of the floor brackets and use the binomial theorem to cancel terms. Keep in mind that $0 < (3 - \sqrt{5})^{34} < 1$.

Solution:
By the binomial theorem and following the hint, we have that $\lfloor (3 + \sqrt{5})^{34} + (3 - \sqrt{5})^{34} \rfloor = \lfloor 2(3^{34} + {34 \choose 2} 3^{32} 5^1 + {34 \choose 4} 3^{30} 5^2 + \dots {34 \choose 4} 3^{4} 5^{15} + {34 \choose 2} 3^2 5^{16} + 5^{17}) \rfloor$. 
The inside is an integer, so we can drop the floor brackets. 
Claim: The sum of the terms not including the first two is divisible by $100$.
Proof: We find that ${34 \choose 2n}$ is even for $2 \leq n \leq 8$ by hand checking. We get a second factor of two from the $2$ multiplying it on the outside. Then all terms with at least $5^2$ as a factor and an even binomial coefficient are divisible by $100$. This deals with all of the terms except for the last two. We can see that the last two terms (without being multiplied by the external $2$) are both odd, so their sum is even. They both have at least $5^2$ as a factor so when they are multiplied by the external $2$ their sum is divisible by $100$.
So, we examine the first two terms. Note that $3^4 \equiv 81, 3^8 \equiv 61, 3^{12} \equiv 41, 3^{16} \equiv 21, 3^{20} \equiv 1 \pmod {100}$. So $3^{34} \equiv 69 \pmod {100}$ and $3^{32} \equiv 41 \pmod {100}$. So we have $2(69 + 33 * 17 * 41 * 5) \equiv 2(69 + 61 * 5) \equiv 48 \pmod {100}$
So we have that $(3 + \sqrt{5})^{34} + (3 - \sqrt{5})^{34} \equiv 48 \pmod {100}$. Since $(3 - \sqrt{5})^{34}$ is between $0$ and $1$, $(3 + \sqrt{5})^{34}$ is between $47$ and $48 \pmod {100}$, so its floor will be $\boxed{47}$.
This is a bit computation heavy, if someone can find a way that is less so I will be happy.
