## approximating square root of nature numbers with Pell’s equation

Posted: December 21, 2012 in Mathematics

This post could be my last post before the world ends, or it could be the celebration for “Hey, we are still alive in the day of doom”.  Last night after I had the last hotpot supper with my friends and a nice sauna at the gym I went home and continue working on my project, but instead I watched youtube and I stumbled upon on an interesting video talking about Diophantine equations and Fermat’s method of ascent.  In the video, he illustrates how to find integral solution of Pell’s equation by Fermat’s method of ascent.  And now I am going to investigate further on Pell’s equation.  In Diophantine equation, we only find solution in integers.

History of Pell’s equation:

So what is Pell’s equation?  There is an interesting story about it.  The equation was named after a mathematician John Pell who didn’t study it.  Euler mistakenly confused William Brouncker, who was the first European studying the equations of this kind, with John Pell.  Pell’s equation is any Diophantine equation of the form:

$x^2-my^2=1$

where $m$ is any positive integer which is not a perfect square.  Why can’t $m$ be a perfect square?  If it is a perfect square, then there exists $t\in\mathbb{Z}$ such that $x^2-(ty)^2=1$.  Contradiction, since the difference between two perfect squares cannot equal to 1.

Method of solving Pell’s equation:

Solving Pell’s equation sometimes isn’t really that difficult.  Let’s say you wanna solve the Pell’s equation

$x^2-2y^2=1$.

The trivial solution would be $x=1$ and $y=0$.  But can you find more solution?  Yes, without any difficulty you should be able to spot another solution of ${x=3, y=2}$.  Then the next question is:  Is there more solution?  And how to find them?  In fact there are infinitely many solution to this Pell’s equation.  They can be found by the following recursive formula:

$x_{n+1}=3x_n+4y_n$

$y_{n+1}=2x_n+3y_n$

So, if

$x_0=3$

$y_0=2$

then

$x_1=3(3)+4(2)=17$

$y_1=2(3)+3(2)=12$

To check it, let’s plug them back to the equation,

$17^2-2(12^2)=289-2(144)=289-288=1$

So indeed it works.  To show that it always work, we need to plug in the $x_{n+1}$ and the $y_{n+1}$

$(x_{n+1})^2-2(y_{n+1})^2=(3x_n+4y_n)^2-2(2x_n+3y_n)^2$

$=9x_n^2+16y_n^2+24x_ny_n-8x_n^2-18y_n^2-24x_ny_x$

$=x_n^2-2y_n^2=1$

Now you may ask “How to figure out the coefficient of 3 and 4 in $x_{n+1}=3x_n+4y_n$ or 2 and 3 in $y_{n+1}=2x_n+3y_n$?”

Here is how you find them:

Let Pell’s equation

$x^2-my^2=1$

with non perfect square $m$.  If $x_0, y_0$ is particular solution such that

$x_0^2-my_0^2=1$,

then let

$x_{n+1}=ax_n+by_n$

$y_{n+1}=cx_n+dy_n$

where $a, b, c, d \in \mathbb{Z^+}$

then

$(x_{n+1})^2-m(y_{n+1})^2=(ax_n+by_n)^2-m(cx_n+dy_n)^2=1$

$a^2x_n^2+b^2y_n^2+2abx_ny_n-mc^2x_n^2-md^2y_n^2-2cdmx_ny_n=1$

then collect like terms and comparing with $x_n^2-my_n^2=1$

$2ab-2cdm=0 \Longrightarrow ab=cdm \Longrightarrow a^2b^2=c^2d^2m^2$

$a^2-mc^2=1 \Longrightarrow a^2=1+mc^2$

$b^2-md^2=-m \Longrightarrow b^2=md^2-m$

hence

$a^2b^2 = md^2-m+c^2d^2m^2-m^2c^2=c^2d^2m^2$

then

$md^2-m-m^2c^2=0$

$d^2-1-mc^2=0$

$d^2-mc^2=1$

Now if $d=x_0, c=y_0$, then

$a^2=1+my_0^2=x_0^2$

$\therefore a=x_0$

$b^2=mx_0^2-m=m(x_0^2-1)=m(my_0^2)$

$\therefore b=my_0$

Therefore,

$x_{n+1}=x_0x_n+my_0y_n$

$y_{n+1}=y_0x_n+x_0y_n$

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

So for $x^2-2y^2=1, m=2, x_0=3, y_0=2$

then

$x_{n+1}=3x_n+4y_n$

$y_{n+1}=2x_n+3y_n$

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

If we divide both sides of the equation $x^2-my^2=1$ by $y^2$, we have

$\left(\dfrac{x}{y}\right)^2-m=\dfrac{1}{y^2}$

$\dfrac{x}{y}=\sqrt{m+\dfrac{1}{y^2}}$

As $y\to\infty, \sqrt{m+\dfrac{1}{y^2}} \to \sqrt{m}$

Therefore we can approximate square root of any non-perfect numbers by Fermat’s method of ascent on Pell’s equation.

For example, to approximate $\sqrt{2}$, takes $m=2, x_0=3, y_0=2, x^2-2y^2=1$

$x_{n+1}=3x_n+4y_n$

$y_{n+1}=2x_n+3y_n$

$x_1=3(3)+4(2)=17$

$y_1=2(3)+3(2)=12$

$x_2=3(17)+4(12)=99$

$y_2=2(17)+3(12)=70$

$x_3=3(99)+4(70)=577$

$y_3=2(99)+3(70)=408$

$x_4=3(577)+4(408)=3363$

$y_4=2(577)+3(408)=2378$

$\therefore \sqrt{2} \approx \dfrac{3363}{2378}$

———————————————————————–

Let’s do one more, $\sqrt{3}$

Consider

$x^2-3y^2=1$

Since $7^2-3(4)^2=1 \Rightarrow x_0=7, y_0=4, m=3$

then

$x_{n+1}=x_0x_n+my_0y_n$

$y_{n+1}=y_0x_n+x_0y_n$

becomes

$x_{n+1}=7x_n+12y_n$

$y_{n+1}=4x_n+7y_n$

$x_1=7(7)+12(4)=97$

$y_1=4(7)+7(4)=56$

$x_2=7(97)+12(56)=1351$

$y_2=4(97)+7(56)=780$

$\therefore \sqrt{3} \approx \dfrac{1351}{780}$

More iterations will achieve better approximation.