Mathacadabra
Home > Advanced Problems > Arithmetic
Note: this page uses MathJax for formatting, so may take a few seconds to load.


A Digital Challenge

If $(\sqrt{2}+\sqrt{3})^{1000}$ is written in decimal notation, say, $a_ka_{k-1}\ldots a_0.b_1b_2 \ldots$, what are $a_0$ and $b_1$?

Solution

Define integer sequences $\{x_n\}$ and $\{y_n\}$ by \[(\sqrt{2}+\sqrt{3})^{2n}=(5+2\sqrt{6})^n=x_n+y_n\sqrt{6}, \quad \mbox{for} \; \, n \geq 0.\] Thus, $\{x_n\}$ and $\{y_n\}$ satisfy the recurrence formula \[ x_0=1,\; y_0=0, \;\; x_{n+1}=5x_n+12y_n, \; y_{n+1}=2x_n+5y_n, \quad \mbox{for} \;\, n \geq 0. \]

From the definition of the sequences, \[ (\sqrt{2}-\sqrt{3})^{2n}=x_n-y_n\sqrt{6}, \] and hence \[ (\sqrt{2}+\sqrt{3})^{2n}+(\sqrt{2}-\sqrt{3})^{2n}=2x_{n}. \]

Since $|\sqrt{2}-\sqrt{3}|<1$, we see that $a_0$ is $2x_{500}-1$ computed modulo $10$, and $b_1=9$. The sequence $\{(x_n,y_n) \bmod{10}\}$ is \[ \{(1,0),(5,2),(9,0),(5,8),\ldots\}, \] where the first four ordered pairs repeat. Hence \[ a_0=2x_0-1=1. \]