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.
On
We use a slight modification of Michael T's approach which reduces the necessary computation and number of technical arguments . Note that $(3+\sqrt{5})^2=14+6\sqrt{5}$. Now $$\lfloor(3+\sqrt{5})^{34}\rfloor=\lfloor(14+6\sqrt{5})^{17}\rfloor=\lfloor(14+6\sqrt{5})^{17}+(14-6\sqrt{5})^{17}\rfloor-1$$ since $14-6\sqrt{5}<1$.
Now expansion with the binomial gives
$$(14+6\sqrt{5})^{17}+(14-6\sqrt{5})^{17}=2(14^{17}+{17\choose 2}14^{15}6^25+{17\choose 4}14^{13}6^45^2+\ldots+6^{16}5^8)$$
Since $6^45^2$ is a multiple of $100$, we immediately find that only the first $2$ terms matter. Note for the following that $7^4=2401\equiv1\pmod{100}$.
First term: $14^{17}2\equiv7^{17}2^{18}\equiv7^{4(4)+1}2^{9(2)}\equiv7(12)^2\equiv7(44)\equiv308\equiv8\pmod{100}$,
Second term: $2(17)(8)14^{15}6^25=10(17)(8)14^{15}6^2$, so we can get rid of a factor of $10$, and
$17(8)14^{15}6^2\equiv(7)2^37^{15}2^{15}2^23^2\equiv2^{20}7^{16}3^2\equiv4^2(1)(-1)\equiv-6\equiv4\pmod{10}$.
Hence the sum of the first two terms is $8+10*4=48 \pmod{100}$, and we conclude that $\lfloor(3+\sqrt{5})^{34}\rfloor\pmod{100}=48-1=47$.
On
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?
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.