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.

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.
