Guojian's Homepage

Square Root of n

Filed under Mathematics on June 5, 2024. Last updated on June 5, 2024.

Table of Contents

Preparation

Last time we talked about 2\sqrt{2}[1] and demonstrated how to calculate the approximate value of 2\sqrt{2}. So what if we want to calculate the square root n\sqrt{n} of any positive integer nn?

When calculating 2\sqrt{2}, there was a key recursive formula:

2=1+11+2\sqrt{2} = 1 + \frac{1}{1+\sqrt{2}}

Careful observation will reveal that 2\sqrt{2} is divided into an integer part 11 and a fractional part 11+2\frac{1}{1+\sqrt{2}}.

If we represent the square root n\sqrt{n} of any positive integer nn as both an integer and a fractional part[2]:

n=⌊n⌋+{n}\begin{align*} \sqrt{n} = \lfloor \sqrt{n} \rfloor + \lbrace \sqrt{n} \rbrace \end{align*}

How can we construct such an equation for n\sqrt{n} and then recursively substitute it to calculate? We can use the difference of squares formula[3] to assist us:

n−⌊n⌋=n−⌊n⌋2n+⌊n⌋=1n+⌊n⌋n−⌊n⌋2\begin{align*} \sqrt{n} - \lfloor \sqrt{n} \rfloor &= \frac{n - {\lfloor \sqrt{n} \rfloor}^2}{\sqrt{n} + \lfloor \sqrt{n} \rfloor} \\ &= \frac{1}{\frac{\sqrt{n} + \lfloor \sqrt{n} \rfloor}{n - {\lfloor \sqrt{n} \rfloor}^2}} \tag{1} \end{align*}

For a specific nn, although we do not yet know the approximate value of n\sqrt{n}, ⌊n⌋\lfloor \sqrt{n} \rfloor can be determined[4]. Use your preferred method to solve for ⌊n⌋\lfloor \sqrt{n} \rfloor.

Solution

Let's try to solve 19\sqrt{19}. It is easy to find that ⌊19⌋=4\lfloor \sqrt{19} \rfloor = 4. Substituting into formula (1),

19−4=119+43=14+{19}+43=18+{19}3\begin{align*} \sqrt{19} - 4 &=\frac{1}{\frac{\sqrt{19} + 4}{3}} \\ &=\frac{1}{\frac{4 + \lbrace \sqrt{19} \rbrace + 4}{3}} \\ &=\frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \end{align*}

Now focus on the denominator part on the right side of the equation. If we want to continue constructing a continued fraction, then consider

(8+{19})/3=2(8+{19})mod  3=2+{19}=2+(19−4)=19−2\begin{align*} (8+\lbrace \sqrt{19} \rbrace) / 3 &= 2 \tag{2}\\ (8+\lbrace \sqrt{19} \rbrace)\mod 3 &= 2 + \lbrace \sqrt{19} \rbrace \\ &= 2 + (\sqrt{19} - 4) \\ &= \sqrt{19} - 2 \tag{3} \end{align*}

Substituting into the equation, we get:

19−4=18+{19}3=12+19−23=12+153(19+2)=12+119+25=12+16+{19}5\begin{align*} \sqrt{19} - 4 &=\frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \\ &=\frac{1}{2 + \frac{\sqrt{19} - 2}{3}} \\ &=\frac{1}{2 + \frac{15}{3(\sqrt{19} + 2)}} \\ &=\frac{1}{2 + \frac{1}{\frac{\sqrt{19} + 2}{5}}} \\ &=\frac{1}{2 + \frac{1}{\frac{6 + \lbrace \sqrt{19} \rbrace}{5}}} \end{align*}

Collecting all the formulas needed in the entire calculation process, we get

19=4+{19}1=4+19−41=4+119+43=4+18+{19}38+{19}3=2+19−23=2+119+25=2+16+{19}56+{19}5=1+19−35=1+119+32=1+17+{19}27+{19}2=3+19−32=3+119+35=3+17+{19}57+{19}5=1+19−25=1+119+23=1+16+{19}36+{19}3=2+19−43=2+119+41=2+18+{19}18+{19}1=8+19−41=8+119+43=8+18+{19}3…\begin{align*} \sqrt{19} = \frac{4 + \lbrace \sqrt{19} \rbrace}{1} &= 4 + \frac{\sqrt{19} - 4}{1} &= 4 + \frac{1}{\frac{\sqrt{19} + 4}{3}} &= 4 + \frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \\ \frac{8 + \lbrace \sqrt{19} \rbrace}{3} &= 2 + \frac{\sqrt{19} - 2}{3} &= 2 + \frac{1}{\frac{\sqrt{19} + 2}{5}} &= 2 + \frac{1}{\frac{6 + \lbrace \sqrt{19} \rbrace}{5}} \\ \frac{6 + \lbrace \sqrt{19} \rbrace}{5} &= 1 + \frac{\sqrt{19} - 3}{5} &= 1 + \frac{1}{\frac{\sqrt{19} + 3}{2}} &= 1 + \frac{1}{\frac{7 + \lbrace \sqrt{19} \rbrace}{2}} \\ \frac{7 + \lbrace \sqrt{19} \rbrace}{2} &= 3 + \frac{\sqrt{19} - 3}{2} &= 3 + \frac{1}{\frac{\sqrt{19} + 3}{5}} &= 3 + \frac{1}{\frac{7 + \lbrace \sqrt{19} \rbrace}{5}} \\ \frac{7 + \lbrace \sqrt{19} \rbrace}{5} &= 1 + \frac{\sqrt{19} - 2}{5} &= 1 + \frac{1}{\frac{\sqrt{19} + 2}{3}} &= 1 + \frac{1}{\frac{6 + \lbrace \sqrt{19} \rbrace}{3}} \\ \frac{6 + \lbrace \sqrt{19} \rbrace}{3} &= 2 + \frac{\sqrt{19} - 4}{3} &= 2 + \frac{1}{\frac{\sqrt{19} + 4}{1}} &= 2 + \frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{1}} \\ \frac{8 + \lbrace \sqrt{19} \rbrace}{1} &= 8 + \frac{\sqrt{19} - 4}{1} &= 8 + \frac{1}{\frac{\sqrt{19} + 4}{3}} &= 8 + \frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \\ \dots \end{align*}

So[5],

19=[4;2,1,3,1,2,8,2,1,3,1,2,8,...]\sqrt{19} = [4;2,1,3,1,2,8,2,1,3,1,2,8,...]

Q&A

Here are brief answers to some of the questions mentioned in the previous article. If there are any inaccuracies, please bear with me.

  1. Why can an equation be substituted into itself? Is this method correct?

    Replacing an equation into itself is essentially the definition of recursion.

  2. For other square root numbers, like 3\sqrt{3}, how can we construct an equation that is similar to the equation for calculating 2\sqrt{2}?

    This article is the answer.

  3. The form of the continued fraction seems similar to the iterative method for finding the greatest common divisor. What is their relationship?

    The iterative method for finding the greatest common divisor essentially breaks down two numbers using smaller numbers continuously. In continued fractions, a similar mechanism operates, as shown in formulas (2) and (3).