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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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]