<s>[INST] 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.
 [/INST] 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?
</s>