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

Question

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?

Answer 1

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.')
```

Answer 2

We work in the rings $$ \begin{aligned} R &=\frac{\Bbb Z[x]}{(x^2-21)}\ ,\\ S = R/(100) &=\frac{\Bbb Z[x]}{(x^2-21)}\Big/(100) =\frac{\Bbb Z[x]}{(x^2-21,\ 100)} =\frac{\Bbb Z_{100}[x]}{(x^2-21)} \end{aligned} $$ I will denote by $A=\sqrt{21}$ the value of $x$ taken modulo $(x^2-21)$ in $R$, and by $a$ the corresponding value in $S$. In these rings we consider the numbers: $$ \begin{aligned} S_k(A) &= (29 + A)^k + (29 - A)^k &&\in\Bbb Z\ ,\\ S_k(a) &= (29 + a)^k + (29 - a)^k &&\in\Bbb Z_{100}\ . \end{aligned} $$ While the value $S_k(A)\in\Bbb Z$ has no easy human chance to be computed for $k=2000$, we have a fairly easy human task when working in $\Bbb Z_{100}:=\Bbb Z/(100)$, in the ring of integers modulo $100$. Over this ring the polynomial in $T$ with the roots $(29\pm a)$ is $T^2-58T+820$ and the "norm" $820$ already tells us that we deal with powers of zero divisors.

So let us compute some powers of $(29\pm a)$ with bare hands, till some $4$-periodicity shows up. $$ \begin{aligned} (29+a)^0 &= 1\ ,\\ (29+a)^1 &= 29+a\ ,\\ (29+a)^2 &= 841 + 58 a + 21 = 862 + 58 a = 62 + 58 a = 2(31 + 29a)\ ,\\ (29+a)^4 &= 2^2(31 + 29a)^2= 4(961 + 58a +17661)=4(22+58a)\\ &=8(11+29a)=88-8a=8(11-a)\ ,\\ (29+a)^8 &= 8^2(11-a)^2=64(121-22a+21)=88-8a=8(11-a)\ ,\\ &\text{ so the positive powers of $8(11-a)$ are $8(11-a)$, so}\\ (29+a)^{4k} &= 8(11-a)\ ,\qquad\text{ and by conjugation}\\ (29-a)^{4k} &= 8(11+a)\ ,\qquad\text{ which gives}\\ S_{4k} &= 8(\ (11-a) +(11+a)\ )= 8\cdot 22=76\ . \end{aligned} $$ $\square$

---

This human solution finds the answer, and also explains how we can and do expect a periodicity for $A_k,B_k$ modulo $100$ with $A_k,B_k\in\Bbb Z$ from the representation $S_k=A_k+B_k\sqrt{21}$, after applying the binomial formula.

In fact, it remains to take the obvious linear recurrence relation of degree two for $S_k$, and thus for $A_k$, $B_k$ from its form in $\Bbb Z$ to its form modulo $100$, and see how fast we get periodicity.

---

And indeed, this result can be easily checked in sage. I am always checking, but please stop reading if computer software feels annoying, a matter of taste.

sage: K.<A> = QuadraticField(21)
sage: S2000 = (29 + A)^2000 + (29 - A)^2000
sage: ZZ(S2000) % 100
76

Note that sage did the computation exactly, we can also ask for

sage: ZZ(S2000) % (10^40)
5666971642218782495869571574855291109376

to have some more digits.

Alternatively, we can work in sage in the ring $S$, as in the above solution:

sage: Z100 = Integers(100)
sage: ZX100.<X> = PolynomialRing(Z100)
sage: S.<a> = ZX100.quotient(X^2 - 21)

sage: for k in [0..16]:
....:     print(f"(29 + a)^{k} = {(29 + a)**k}")
(29 + a)^0 = 1
(29 + a)^1 = a + 29
(29 + a)^2 = 58*a + 62
(29 + a)^3 = 44*a + 16
(29 + a)^4 = 92*a + 88
(29 + a)^5 = 56*a + 84
(29 + a)^6 = 8*a + 12
(29 + a)^7 = 44*a + 16
(29 + a)^8 = 92*a + 88
(29 + a)^9 = 56*a + 84
(29 + a)^10 = 8*a + 12
(29 + a)^11 = 44*a + 16
(29 + a)^12 = 92*a + 88
(29 + a)^13 = 56*a + 84
(29 + a)^14 = 8*a + 12
(29 + a)^15 = 44*a + 16
(29 + a)^16 = 92*a + 88
sage: S2000 = (29 + a)^2000 + (29 - a)^2000
sage: S2000
76

Finally, here are some last digits of the first $S_k$, with $k\in 0,1,\dots,20$:

sage: def S(k):    return ZZ( (29 +  A)^k + (29 - A)^k )
sage: for k in [0..20]:
....:     print(f"S({k}) = {S(k)}")
S(0) = 2
S(1) = 58
S(2) = 1724
S(3) = 52432
S(4) = 1627376
S(5) = 51393568
S(6) = 1646378624
S(7) = 53347234432
S(8) = 1744109125376
S(9) = 57413597037568
S(10) = 1899819145370624
S(11) = 63110360860690432
S(12) = 2102549230716133376
S(13) = 70197359475769581568
S(14) = 2347356480407406362624
S(15) = 78584841093498512146432
S(16) = 2633088469488840487141376
S(17) = 88279561533683968294125568
S(18) = 2961082023972820961603354624
S(19) = 99353516932802761771811602432
S(20) = 3334416722444846994250322149376
sage: 

Answer 3

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.$$