4
$\begingroup$

Solve Pell's equation $x^2-5y^2=\pm4$.

This equation arises when I tried to prove that the units of $\mathbb{Z}[\varphi]$, where $\varphi=\frac{1+\sqrt{5}}{2}$ is the golden ratio, are of the form $\pm\varphi^n$. I found that $x+\varphi y$ is a unit iff $x^2+xy-y^2=\pm1$, i.e. $(2x+y)^2-5y^2=\pm4$. Yet I am unable to solve this equation. I saw here a solution using algebraic number theory, but I am interested in how to solve this equation using elementary methods, without using results from algebraic number theory. Thanks in advance!

$\endgroup$
5
  • $\begingroup$ I put the full diagram at math.stackexchange.com/questions/512621/… I typed in the $-4$ and you can read off the $+4$ $\endgroup$ – Will Jagy Jun 3 '17 at 3:23
  • $\begingroup$ It seems that your solution uses too many results with which I'm not familiar... Is there any solution using, say, continued fractions? $\endgroup$ – Colescu Jun 3 '17 at 3:31
  • $\begingroup$ If you want an "elementory" method, maybe continued fractions? Calculate your partial quotients, $a_n$ and the corresponding values of $p_n$ and $q_n$(I can't remember if these quantities had names) and then compute $p_n^2-Nq_n^2$. Eventually the $p_n^2-Nq_n^2$ becomes periodic so you just want to see if there are any values of $p_n$ and $q_n$ that gives you $\pm 1,\pm 4$ $\endgroup$ – daruma Jun 3 '17 at 3:33
  • 1
    $\begingroup$ In general there are no solutions or there are infinitely many solutions. $\endgroup$ – daruma Jun 3 '17 at 3:36
  • $\begingroup$ @daruma Could you please elaborate? I'm unsure what to do... $\endgroup$ – Colescu Jun 3 '17 at 3:58
2
$\begingroup$

Let's take a solution $(x,y)$ of $x^2-5y^2=\pm4$. Assume $x>0$ and $y>0$. Clearly also $x$ and $y$ have the same parity. Define $$x'=\frac{5y-x}2,\qquad y'=\frac{x-y}2.$$ Then $x'$ and $y'$ are integers, and $$x'^2-5y'^2=\frac{(5y-x)^2-5(x-y)^2}4=\frac{20y^2-4x^2}4=\pm4.$$ Therefore $(x',y')$ is also a solution. I claim that $y'\ge0$ and $x'>0$.

If $y'<0$ then $x<y$ and $x^2-5y^2<-4x^2<-4$, which is false. So $y'\ge0$. If $x'\le0$ then $x\ge5y$ and $x^2-5y^2\ge20y^2>4$ which is false. So $y'\ge0$.

I claim that as long as $y\ge2$, then $y'<y$. Otherwise, $x\ge3y$ and $\pm 4=x^2-5y^2\ge4y^2$. This is only possible if $y=1$.

So, iterating the operation $(x,y)\mapsto(x',y')$ eventually reduces $(x,y)$ to a solution $(X,Y)$ with $X>0$ and $Y\in\{0,1\}$. Therefore to $(X,Y)=(2,0)$, $(1,1)$ or $(3,1)$. All of these reduce down to $(2,0)$.

Therefore we can start with $(x_0,y_0)=(2,0)$ and reversing the operation generate all positive solutions. The iterative process is $$(x_{n+1},y_{n+1})=\left(\frac{x+5y}2,\frac{x+y}2\right).$$

$\endgroup$
7
  • $\begingroup$ Wow, that was brilliant! Is this a method that could be used to solve other Pell equations or is it just designed for this specific problem? $\endgroup$ – Colescu Jun 3 '17 at 4:42
  • $\begingroup$ @YuxiaoXie It is just a translation of the algebraic number theory method into elementary language, knowing that the fundamental unit is $\frac12(1+sqrt5)$. $\endgroup$ – Angina Seng Jun 3 '17 at 4:43
  • $\begingroup$ How did you get $(5y-x)/2$ and $(x-y)/2$ then? Through algebraic number theory? $\endgroup$ – Colescu Jun 3 '17 at 4:50
  • $\begingroup$ @YuxiaoXie Just dividing $x+y\sqrt5$ by $\frac12(1+\sqrt5)$. $\endgroup$ – Angina Seng Jun 3 '17 at 4:51
  • $\begingroup$ Though this may lead to another question, I feel compelled to ask, is it possible to generalize this to other Pell equations of the form $x^2-dy^2=k$ and how? $\endgroup$ – Colescu Jun 3 '17 at 4:55
2
$\begingroup$

A little better format. Given any solution to $u^2 - 5 v^2 = \pm 4$ with large positive $u,v,$ a smaller solution can be constructed using $$ (u,v) \mapsto (9 u - 20 v, \; -4 u + 9 v). $$ As a result, we get a finite number of "seed" solutions, those being $u,v,\geq 0$ with either $9u - 20 v < 0$ or $-4u + 9v < 0.$ The set of such seeds is guaranteed finite; with large positive values and $u^2 - 5 v^2 = \pm 4,$ we have $u/v \approx \sqrt 5 \approx 2.236,$ arbitrarily close. The seed pairs have either $u/v < 2.22222$ or $u/v > 2.250.$

Put it together, all solutions are given by $u$ a Lucas number and $v$ Fibonacci.

======================================

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental_plus_minus
  automorphism matrix:  
    9   20
    4   9
   backwards:  
    9   -20
    -4   9

  9^2 - 5 4^2 = 1

 u^2 - 5 v^2 = +- 4

Sat Jun  3 11:46:39 PDT 2017

u:  2  v:  0  SEED   KEEP +- 
u:  1  v:  1  SEED   BACK ONE STEP  -11 ,  5
u:  3  v:  1  SEED   KEEP +- 
u:  4  v:  2  SEED   BACK ONE STEP  -4 ,  2
u:  7  v:  3  SEED   BACK ONE STEP  3 ,  -1
u:  11  v:  5  SEED   BACK ONE STEP  -1 ,  1
u:  18  v:  8
u:  29  v:  13
u:  47  v:  21
u:  76  v:  34
u:  123  v:  55
u:  199  v:  89
u:  322  v:  144
u:  521  v:  233
u:  843  v:  377
u:  1364  v:  610
u:  2207  v:  987
u:  3571  v:  1597
u:  5778  v:  2584
u:  9349  v:  4181
u:  15127  v:  6765
u:  24476  v:  10946
u:  39603  v:  17711
u:  64079  v:  28657
u:  103682  v:  46368
u:  167761  v:  75025
u:  271443  v:  121393
u:  439204  v:  196418
u:  710647  v:  317811
u:  1149851  v:  514229
u:  1860498  v:  832040
u:  3010349  v:  1346269
u:  4870847  v:  2178309
u:  7881196  v:  3524578
u:  12752043  v:  5702887

Sat Jun  3 11:46:59 PDT 2017

 u^2 - 5 v^2 = 4

jagy@phobeusjunior:~$

=======================================

Same problem with $13$ rather than $5.$ Instead of $u_{n+2} = u_{n+1} + u_n,$ this time we get $u_{n+2} = 3 u_{n+1} + u_n.$

=====================================

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental_plus_minus
  automorphism matrix:  
    649   2340
    180   649
   backwards:  
    649   -2340
    -180   649

  649^2 - 13 180^2 = 1

 u^2 - 13 v^2 = +- 4

Sat Jun  3 17:46:55 PDT 2017

u:  2  v:  0  SEED   KEEP +- 
u:  3  v:  1  SEED   BACK ONE STEP  -393 ,  109
u:  11  v:  3  SEED   KEEP +- 
u:  36  v:  10  SEED   BACK ONE STEP  -36 ,  10
u:  119  v:  33  SEED   BACK ONE STEP  11 ,  -3
u:  393  v:  109  SEED   BACK ONE STEP  -3 ,  1
u:  1298  v:  360
u:  4287  v:  1189
u:  14159  v:  3927
u:  46764  v:  12970
u:  154451  v:  42837
u:  510117  v:  141481
u:  1684802  v:  467280
u:  5564523  v:  1543321
u:  18378371  v:  5097243

Sat Jun  3 17:47:25 PDT 2017

 u^2 - 13 v^2 = +- 4

jagy@phobeusjunior:~$

=====================================

This time 29

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental_plus_minus
  automorphism matrix:  
    9801   52780
    1820   9801
   backwards:  
    9801   -52780
    -1820   9801

  9801^2 - 29 1820^2 = 1

 u^2 - 29 v^2 = +- 4

Sat Jun  3 17:54:38 PDT 2017

u:  2  v:  0  SEED   KEEP +- 
u:  5  v:  1  SEED   BACK ONE STEP  -3775 ,  701
u:  27  v:  5  SEED   KEEP +- 
u:  140  v:  26  SEED   BACK ONE STEP  -140 ,  26
u:  727  v:  135  SEED   BACK ONE STEP  27 ,  -5
u:  3775  v:  701  SEED   BACK ONE STEP  -5 ,  1
u:  19602  v:  3640
u:  101785  v:  18901
u:  528527  v:  98145
u:  2744420  v:  509626
u:  14250627  v:  2646275

Sat Jun  3 17:55:38 PDT 2017

 u^2 - 29 v^2 = +- 4

jagy@phobeusjunior:~$

==============================

$\endgroup$
2
  • $\begingroup$ What do these mean? $\endgroup$ – Colescu Jun 3 '17 at 4:34
  • $\begingroup$ @YuxiaoXie revised the answer. Comes out Fibonacci and Lucas; Also, about as elementary as is possible. $\endgroup$ – Will Jagy Jun 3 '17 at 19:47
0
$\begingroup$

There is a good story of solutions in Wikipedia. For the solution of Pell's

like equation x^2−Dy^2=±C^2. You can always use following simple algorithm:

A:

x^2−5y^2 = 4

suppose x = y + a then we have:

y^2+2ay+a^2 -5y^2= 4 or 4y^2-2ay-a^2+4=0

y= [a±(5a^2-16)^0.5]/4

with a= 10 we get y = 8 and x = 10 + 8 = 18

I guess there is more solutions in N for this equation.

with a=0 we get complex solutions x = y = ±i and with any a other than these

two we may get real solutions but it must be checked in the equation.

B:

For equation x^2−5y^2 = -4 assuming again x = y+a we get:

4y^2 - 2ay -a^2-4=0

y = [a±(5a^2+16)^0.5]/4

with a=2 we get y =2 and y=-1 ; if y=-1 then x=±1 these are solutions in R. There may be infinitely many solutions in R .

With a=6 we get y=5 and x = 6+5=11. More solutions in N is probable.

with a=0 we get y = x = ±1

Generally there is an algorithm that says there can be infinitely many Pell's like equations in which triples x, D and y are functions of a parameter like m.Now I solve equation x^2−5y^2 = 4 with this algorithm:

Suppose x=m^2 +2 we have:

m^2(m^2+4) = 5y^2

if y^2=m^2 then y = ±m and also:

m^2 +4 = 5 ; m=±1 which results x = 3

and triples (x, D, y)=(m^2+2, 5m, ±m) for m=-1 and

(x, D, y) = (m^2+2, -5m, ±m) for m=1.

Now we can make more Pell's like equations; for example with m =2 we have:

D = 5 . 2 =10 that gives x^2 -10y^2 = 16 which it's solutions are x=2^2 +2 =6

and y=±2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.