106. Check that in 3-adic arithmetic 201 is a square root of the number ...112101 with an accuracy of three digits.

Let us assume we have already found $B_{n}$. We will show how to find $B_{n+1}$ - the square root of $A$ with an accuracy of $n+1$ digits. We seek $B_{n+1}$ in the form

$$
B_{n+1}=B_{n}+x \cdot 10^{n}
$$

where $x$ is a single-digit $p$-adic number $(x \cdot 10^{n}=x \underbrace{00 \ldots 00}_{n \text { zeros }})$.

1) We use the notation 201 instead of ...000201. Any finite number in the $m$-ary system can be considered as $m$-adic in this way.
2) Note that the number $p$ in $p$-adic arithmetic is written as 10.

Raising $B_{n+1}$ to the square, we get

$$
B_{n+1}^{2}=B_{n}^{2}+2 B_{n} \cdot x \cdot 10^{n}+x^{2} \cdot 10^{2 n}
$$

from which

$$
2 B_{n} \cdot x \cdot 10^{n}=B_{n+1}^{2}-B_{n}^{2}-x^{2} \cdot 10^{2 n}
$$

We need the last $n+1$ digits of $B_{n+1}^{2}$ and $A$ to coincide. From formula (1), it follows that for this it is necessary and sufficient that the last $n+1$ digits of the number $2 \cdot B_{n} \cdot x \cdot 10^{n}$ be the same as those of the number $A-B_{n}^{2}-x^{2} \cdot 10^{2 n}$, or, equivalently, of the number $A-B_{n}^{2}$ (since $x^{2} \cdot 10^{2 n}$ ends with $2 n$ zeros).

Thus, the last $n+1$ digits of the numbers $2 B_{n} \cdot x \cdot 10^{n}$ and $A^{2} - B_{n}^{2}$ must coincide. Both $2 B_{n} \cdot x \cdot 10^{n}$ and $A^{2}-B_{n}^{2}$ end with $n$ zeros, so the last $n$ digits coincide automatically. Let the last digit of the number $B_{n}$ be $b$ (since by condition the last digit of $A$ is not zero, then $b \neq 0$). Then the last digit of the number $2 B_{n}$ is $c=2 b$ (the $p$-adic product of 2 and $b$), and $c \neq 0$ since $p \neq 2$ and $b \neq 0$. In this case, $c$ is the $(n+1)$-th digit from the right of the number $2 B_{n} \cdot 10^{n}$, and the $(n+1)$-th digit of the number $2 B_{n} \cdot 10^{n} \cdot x$ is $c x$ (the $p$-adic product of $c$ and $x$). Denoting the $(n+1)$-th digit of the number $A^{2}-B_{n}^{2}$ by $d$, we have

$$
c x=d
$$

from which $x=\frac{d}{c}$ in $p$-adic arithmetic (since $c \neq 0$, division is possible). Thus, we have found $B_{n+1}$. Note that the last $n$ digits of $B_{n+1}$ and $B_{n}$ coincide.

Example. Find the square root with an accuracy of four digits of the 3-adic number ...112101. The root with an accuracy of three digits we already know (problem 106); it is 201. We seek the required number in the form $\left(201+x \cdot 10^{3}\right)$. We have

$$
\begin{aligned}
\left(201+x \cdot 10^{3}\right)^{2}=201^{2}+ & 2 \cdot 201 \cdot x \cdot 10^{3}+x^{2} \cdot 10^{6}= \\
& =111101+1102000 \cdot x+x^{2} \cdot 10^{6}
\end{aligned}
$$

The last four digits of this number must coincide with the corresponding digits of the number ...112101. This is equivalent to the last four digits of the number $1102000 \cdot x$ being equal to the last four digits of the number

$$
...112101-111101-x^{2} \cdot 10^{6}=...001000
$$

The fourth digit from the right of the number $1102000 \cdot x$ is $2 x$ (in 3-adic arithmetic), and for the number (2) this digit is 1, from which

$$
2 x=1 \quad \text { (in } 3 \text {-adic arithmetic) }
$$

and $x=2$. We leave it to the reader to verify that $201+$ $+2 \cdot 10^{3}=2201$ is indeed the square root of $\ldots 112101$ with an accuracy of four digits.

Now we are able to construct the square root of a $p$-adic number $A$. Let the last digit of the number $A$ be $a_{1}$. If $\sqrt{a_{1}}$ can be extracted in $p$-adic arithmetic, then $a_{1}=b_{1}^{2}$ (in $p$-adic arithmetic). Then the $p$-adic number $B_{1}=\ldots 00 b_{1}$ is the square root of $A$ with an accuracy of one digit. Using our method, we can construct $B_{2}, B_{3}, \ldots, B_{n}, \ldots$ successively.

Let us write these numbers one under the other:

$$
\begin{aligned}
& \ldots . . b_{1}=B_{1} \\
& \ldots . b_{2} b_{1}=B_{2} \\
& \ldots . b_{3} b_{2} b_{1}=B_{3}, \\
& \ldots b_{4} b_{3} b_{2} b_{1}=B_{4}
\end{aligned}
$$

The digits on the main diagonal of this table form the $p$-adic number $B=\ldots b_{4} b_{3} b_{2} b_{1}$. It is easy to see that $B^{2}=A$.

Taking into account problem 105, we thus obtain the following result:

Let $p \neq 2$ and the last digit of the $p$-adic number $A$ be different from zero; then the square root of $A$ can be extracted if and only if the square root of the last digit of $A$ can be extracted in $p$-adic arithmetic.

## CHAPTER III  APPLICATIONS OF $m$-ARITHMETIC AND $p$-ARITHMETIC TO NUMBER THEORY

## § 1. Fibonacci Sequence

The sequence of numbers

$$
u_{0}, u_{1}, u_{2}, u_{3}, \ldots, u_{n}, \ldots
$$

is called a Fibonacci sequence (briefly, sequence F) if each of its members, starting from $u_{2}$, is equal to the sum of the two preceding members, i.e.,

$$
u_{n}=u_{n-2}+u_{n-1} \quad(\text { for } n \geqslant 2)
$$

Thus, the sequence $\Phi$ is completely determined if the two initial members $u_{0}$ and $u_{1}$ are given.

By choosing different numbers for $u_{0}$ and $u_{1}$, we obtain different Fibonacci sequences. Among these sequences, a special role is played by the sequence starting with the numbers 0,1, i.e., the sequence

$0,1,1,2,3,5,8,13,21,34,55,89,144,233, \ldots$

We agree to call this sequence the sequence $\Phi^{0}$ and denote its members by the letters $a_{0}, a_{1}, a_{2}, \ldots$ :

$a_{0}=0, \quad a_{1}=1, a_{2}=1, \quad a_{3}=2, a_{4}=3, a_{5
106. Indeed,

$$
\begin{aligned}
& \begin{array}{r}
201 \\
\times \frac{201}{201}
\end{array} \\
& 000 \\
& 1102 \\
& 111101
\end{aligned}
$$

The last three digits of the numbers 111101 and ... 112101 coincide.