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.

Advertisements
Comments
  1. Ellis Pearson says:

    is there a way to find x(0) and y(0) without trial and error?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s