# Pell's equation (or a special case of a second order diophantine equation)

Question Find integers $x,y$ such that $$x^2-119y^2=1.$$

So far I've tried computing the continued fraction of $\sqrt{119}$ to find the minimal solution, but either I messed up or I don't know where to stop computing a rough approximation of said square root. Please help.

• I think one can't approximate in getting the continued fraction. The solution depends on the full period of the continued fraction, whether it has odd or even length, etc., and erroneous terms will throw that off. – coffeemath Sep 3 '18 at 7:50
• alpertron.com.ar/QUAD.HTM – Ivan Neretin Sep 3 '18 at 10:23

We will compute the continued fraction by the following algorithm (may or may not be the most efficient way in doing this, but it's the way I was taught!):

We set the following $$x:=\sqrt{119},\quad x_0=x,\quad a_i=\lfloor x_i\rfloor,\quad x_{i+1}=(x_i-a_i)^{-1},$$

and then we stop once we reach a loop in $x_i$ terms and list those terms as the continued fraction.

So, carrying out this procedure gives $$x_0=\sqrt{119},\quad a_0=\lfloor\sqrt{119}\rfloor=10,$$ $$x_1=\frac{1}{\sqrt{119}-10}=\frac{\sqrt{119}+10}{19},\quad a_1=\lfloor\frac{\sqrt{119}+10}{19}\rfloor=1,$$ $$x_2=\frac{1}{\frac{\sqrt{119}+10}{19}-1}=\frac{1}{\frac{\sqrt{119}-9}{19}}=\frac{19}{\sqrt{119}-9}=\frac{19(\sqrt{119}+9)}{38}=\frac{\sqrt{119}+9}{2},\quad a_2=\lfloor \frac{\sqrt{119}+9}{2}\rfloor=9,$$ $$x_3=\frac{1}{\frac{\sqrt{119}+9}{2}-9}=\frac{\sqrt{119}+9}{19},\quad a_3=\lfloor\frac{\sqrt{119}+9}{19}\rfloor=1,$$ $$x_4=\frac{1}{\frac{\sqrt{119}+9}{19}-1}=10+\sqrt{119},\quad a_4=\lfloor10+\sqrt{119}\rfloor=20,$$ $$x_5=\frac{1}{10+\sqrt{119}-20}=\frac{1}{\sqrt{119}-10}=x_1.$$ Since we have reached a loop in terms, we stop. Thus $$\sqrt{119}=[10;\overline{1,9,1,20}].$$ From here, we note that the period of this continued fraction is $4$ and so, the fundamental solution arises in the third partial convergent. We compute it as follows $$[10;1,9,1]=10+\frac{1}{1+\frac{1}{9+\frac{1}{1+1}}}=\frac{120}{11}.$$ So the pair $(120,11)$ is the smallest solution. Indeed $$120^2-119\times 11^2=1.$$ Finally, to generate all the solutions to this equation, we take the form $$(120+11\sqrt{119})^n,$$ where $n\in\Bbb N$.

The algorithm in the first answer works for the general case, but in this specific case, noticing that $119$ is very close to the perfect square $121$ suggests that $y=11$ is worth a look. Then, $119\cdot 121=(120-1)(120+1)=120^2-1$ leads directly to $x=120, y=11$ as a solution.

COMMENT.-To solve the Pell-Fermat equation $a^2-db^2=1$ (or $-1$) the true problem is the calculation of the fundamental unit of $\mathbb Q(\sqrt d)$. Another way is the following algorithm (Pierre Samuel):

Since $a_n+b_n\sqrt d=(a_1+b_1\sqrt d)^n$ we have easily the relation $a_1b_n+b_1b_n=b_{n+1}$ where the sequence of $b_n$ is increasing so one can calculate the numbers $db^2$ for $b\ge1$ and stop when $db^2+1$ is an square. In your case $d=119$ and we have the numbers $$119\cdot1\\119\cdot4=476\\119\cdot9\\\cdots\\\cdots\\119\cdot100=11900\\119\cdot121=14399$$

it is apparent that $14399+1=14400$ which is an obvious square so we get $a_1+b_1\sqrt{11}=\sqrt{14400}+11\sqrt{119}=120+11\sqrt{119}$.

Whatever the used algorithm, it is clear that the procedure could be tedious for many values of $d$. In this example discarding of the ten first numbers was immediate at a glance.

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

$(x-1)(x+1)=119 y^2$

$x-1=119 ⇒ x=120$

$x+1=y^2$

subtracting two equations we get:

$y^2-119=2$

$y^2=121 ⇒ y=±11$

• Your second line can have other solutions than the one you give, though. – Arnaud D. Sep 3 '18 at 16:20
• This approach makes evident that $y$ can be $11$ or $-11$; but reflection then would suggest that $x$ can be $120$ OR $-120$, which none of the answers directly identified. – Keith Backman Sep 4 '18 at 13:28

Another way to solve the Pell equation in Pell’s equation without irrational numbers by Norman Wildberger.

Example find smallest solution in pari/gp:

njw(d)=
{
L= [1,0;1,1]; R= [1,1;0,1];
A= [1,0;0,-d]; Q= A; N= 1;
while(1,
a= Q[1,1]; b= Q[1,2]; c= Q[2,2];
t= a+2*b+c;
if(t<0, Q= R~*Q*R; N= N*R, Q= L~*Q*L; N= N*L);
if(Q==A, break())
);
return(N[,1]~)
};

? njw(119)
%2 = [120, 11]