Find the two last digits of $[(29+\sqrt{21})^{2000}]$.

Let $n=\left[(29+\sqrt{21})^{2000}\right]$. I want to find the two last digits of $n$. I known that, $S_k=(29+\sqrt{21})^{2000}+(29-\sqrt{21})^{2000}$ is integer, but from this I could not find the integer part of $(29+\sqrt{21})^{2000}$.

How to find them?

Given the conjugate $29-\sqrt{21}>1$ and the lack of periodicity(*), your best bet is probably to compute the coefficient $(29+\sqrt{21})^n=A_n+B_n\sqrt{21}$, $A_n,B_n\in\mathbb{Z}$ and a very tight bound on $\sqrt{21}$ using the convergents from the continued fraction $\sqrt{21}=[4;\overline{1,1,2,1,1,8}]$. Note that while you can use the value $A_{2000}\mod 100$ you cannot take this shortcut for $B_{2000}$, so you will be manipulating huge fractions thousands of decimal digits long, i.e., a task probably best left for arbitrary precision arithmetics on the computer or else be prepared to have many sheets of paper even just to write down one step of the calculation (you need more than 748 full period, with more than 1500 decimal digits in the numerator and denominator just for $\sqrt{21}$. Add another 3000 for $B$). As you can see from WolframAlpha list, the answer WolframAlpha gives is 43, which my little python program(**) implementing exactly the procedure outlined above agrees.

(*) Even for $x_n=\lfloor (29+\sqrt{21})^n\rfloor\mod 4$ the sequence starts with \begin{multline} x_0=1, x_1=1, x_2=3, x_3=2, x_4=0,\\ x_5=1, x_6=0, x_7=3, x_8=1, x_9=1,\dots \end{multline} and we don't see $1,1,3,2,0$ again until $n=2500$ which gives \begin{multline} x_{2500}=1,x_{2501}=1,x_{2502}=3,x_{2503}=2,x_{2504}=0,\\ x_{2505}=2,x_{2506}=1,x_{2507}=0,x_{2508}=3,x_{2509}=3,\dots \end{multline}

(**) Python program:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n = 2000
A = 1
B = 0

for i in range(n):
    A_new = 29*A + 21*B
    B_new = A + 29*B
    A = A_new
    B = B_new

def sqrt21_iter():
    """ return iterator for convergents (p_n,q_n) """
    c_old = (4, 1)
    yield c_old
    c_new = (5, 1)
    yield c_new
    sqrt21m4_ref = (1,1,2,1,1,8)
    sqrt21m4 = sqrt21m4_ref[1:] + (sqrt21m4_ref[0],)
    while True:
        for j in sqrt21m4:
            c = (j * c_new[0] + c_old[0], j*c_new[1]+c_old[1])
            c_old = c_new
            c_new = c
            yield c

old = False
new = True
myiter = sqrt21_iter()
while old != new:
    sqrt21 = next(myiter)
    old = new
    new = (B * sqrt21[0])//sqrt21[1]
    print(f'\\sqrt{{21}}={sqrt21[0]}/{sqrt21[1]}, B\\sqrt{{21}}={new}, floor(A+B\\sqrt{{21}})={new+A}')
outstr.append('Result converged.  Stopping.')
```

Denote \begin{cases} S_k=(29+\sqrt{21})^k+(29-\sqrt{21})^k\\[4pt] R_k=(29+\sqrt{21})^k-(29-\sqrt{21})^k\\[4pt] Q_k=\dfrac1{\sqrt{21\mathstrut}}R_k\\[4pt] P_k=(29+\sqrt{21})^k(29-\sqrt{21})^k,\tag1 \end{cases} then

\begin{cases} P_k=820^k,\quad S_{2k}=S_k^2-2P_k=21Q_k^2+2P_k,\\ 21Q_k^2+4P_k=S_k^2,\quad S_{2k}=\dfrac12\left(S_k^2+21Q_k^2\right),\quad Q_{2k}=S_kQ_k,\tag2 \end{cases} \begin{cases} S_{3k}=S_k(S_k^2-3P_k)=\dfrac14S_k\left(S_k^2-63Q_k^2\right)\\ Q_{3k}=Q_k\left(21Q_k^2+3P_k\right)=\dfrac14Q_k\left(S_k^2+63Q_k^2\right)\\ S_{4k}=\dfrac12\left(S_{2k}^2+21Q_{2k}^2\right)=\dfrac18\left(S_k^4+126S_k^2Q_k^2+441Q_k^4\right)\\ Q_{4k}=S_{2k}Q_{2k}=\dfrac12S_kQ_k\left(S_k^2+21Q_k^2\right)\\ S_{5k}=S_k\left(S_{4k}-P_kS_{2k}+P_{k}^2\right) =\dfrac1{16}S_k\left(S_k^4+210S_k^2Q_k^2+2205Q_k^2\right)\\ Q_{5k}=Q_k\left(S_{4k}+P_kS_{2k}+P_k^2\right) =\dfrac1{16}Q_k\left(5S_k^4+210S_k^2Q_k^2+441Q_k^2\right).\tag3 \end{cases}

The table below by Wolfram Alpha contains the directly calculated values $\,Q_k\,$ and $\,S_k\,$ which can be used for the formulas $(2)-(3)$ verification.

From $(2)-(3)$ should: $$Q_{2k}=Q_k\sqrt{21Q_k^2+4P_k},\tag4$$ $$Q_{5k}=\dfrac1{16}Q_k\left(5\left(21Q_k^2+4P_k\right)^2+210Q_k^2\left(21Q_k^2+4P_k\right)+441Q_k^4\right)$$ $$=Q_k\left(441Q_k^4+105P_kQ_k^2+5P_k^2\right),$$ $$4Q_{5k}=Q_k\left(5\left(2P_k+21Q_k^2\right)^2-(21Q_k^2)^2\right).\tag5$$

Therefore, $$Q_1=\dfrac{2\sqrt{21}}{\sqrt{21}}=2,$$ $$Q_2=2\sqrt{21\cdot2^2+4\cdot820}=2\cdot58=116,$$ $$Q_4=116\sqrt{21\cdot116^2+4\cdot820^2}=116\cdot1724=199984,$$ $$Q_8=199984\sqrt{21\cdot199984^2+4\cdot820^4}=19984\cdot1627376=325\,449\,161\,984,$$ $$Q_{16}=Q_8\sqrt{21\cdot Q_8^2+4\cdot820^8} =567\,618\,853\,262\,266\,388\,905\,984.$$ And now, applying $(5)$ for $\;k=16,80,400\;$ in the forms of $$Q_{80}=\dfrac14Q_{16}\left(5\left(2\cdot820^{16}+21Q_{16}^2\right)^2-(21Q_{16}^2)^2\right),\tag{5$\text a$}$$ $$Q_{400}=\dfrac14Q_{80}\left(5\left(2\cdot820^{80}+21Q_{80}^2\right)^2-(21Q_{80}^2)^2\right),\tag{5$\text b$}$$ $$Q_{2000}=\dfrac14Q_{400}\left(5\left(2\cdot820^{400}+21Q_{400}^2\right)^2-(21Q_{400}^2)^2\right),\tag{5$\text c$}$$ one can check that the last decimal digits of the $\;R_{2000}\,$ correspond to the condition

$$r=\left\lfloor Q_{2000}\sqrt{21}\right\rfloor \mod 200 = 110\tag6$$ (see also WA calculations).

At the same time, by the periodicity $$s= S_{2000}\mod 200 = 176.\tag7$$ Therefore,

$$n=\left\lfloor(29+\sqrt{21})^{2000}\right\rfloor\mod 100 =\genfrac\lfloor\rfloor{}0{s+r}2 \mod 100 =43.$$