# Solving Pell's equation $x^2-5y^2=\pm4$ using elementary methods.

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!

• I put the full diagram at math.stackexchange.com/questions/512621/… I typed in the $-4$ and you can read off the $+4$ – Will Jagy Jun 3 '17 at 3:23
• It seems that your solution uses too many results with which I'm not familiar... Is there any solution using, say, continued fractions? – Colescu Jun 3 '17 at 3:31
• 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$ – daruma Jun 3 '17 at 3:33
• In general there are no solutions or there are infinitely many solutions. – daruma Jun 3 '17 at 3:36
• @daruma Could you please elaborate? I'm unsure what to do... – Colescu Jun 3 '17 at 3:58

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).$$

• 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? – Colescu Jun 3 '17 at 4:42
• @YuxiaoXie It is just a translation of the algebraic number theory method into elementary language, knowing that the fundamental unit is $\frac12(1+sqrt5)$. – Angina Seng Jun 3 '17 at 4:43
• How did you get $(5y-x)/2$ and $(x-y)/2$ then? Through algebraic number theory? – Colescu Jun 3 '17 at 4:50
• @YuxiaoXie Just dividing $x+y\sqrt5$ by $\frac12(1+\sqrt5)$. – Angina Seng Jun 3 '17 at 4:51
• 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? – Colescu Jun 3 '17 at 4:55

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:~$


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

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

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.