Pell's equation (simple solutions)

Pell's equation is any Diophantine equation of the form $x^2 – Dy^2 = 1,$ where $D$ is a given positive nonsquare integer, and integer solutions are sought for $x$ and $y.$

Denote the sequence of solutions $\{x_i, y_i \}.$ It is clear that $\{x_0, y_0 \} = \{1,0 \}.$

During the solution we need:

a) to construct a recurrent sequence $\{x_{i+1}, y_{i+1} \} = f({x_i, y_i})$ or two sequences $\{x_{i+1} \} = f({x_i}), \{y_{ i+1} \} = g({y_i});$

b) to prove that the equation has no other integer solutions.

Equation of the form $x^2 – 2y^2 = 1$

Prove that all positive integer solutions of the equation $x^2 – 2y^2 = 1$ can be found using recursively transformation $x_{i+1} = 3 x_i + 4 y_i , y_{i+1} = 2 x_i + 3 y_i$ of the pare $\{x_0, y_0\} = \{1,0\}.$

Proof

$\boldsymbol{a.}$ Let integers $(x_i, y_i)$ are the solution of the equation $\hspace{10mm} x_i^2 - 2 y_i^2 = 1,$ $\begin{equation} \left\{ \begin{aligned} x_{i+1} &= 3 x_i + 4 y_i ,\\ y_{i+1} &= 2 x_i + 3 y_i . \end{aligned} \right.\end{equation}$ Then $x_{i+1}^2 - 2 y_{i+1}^2 = (3 x_i + 4 y_i)^2 - 2 (2 x_i + 3 y_i)^2 = x_i^2 - 2 y_i^2 = 1.$

Therefore integers $(x_{i+1}, y_{i+1})$ are the solution of the given equation. If $i > 0$ then $x_{i+1} > y_{i+1} \ge 2(x_i + y_i) > x_i > y_i > 0.$ $\{(x_i, y_i) \} = \{(1,0), (3,2), (17,12), (99,70),...\}.$

$\boldsymbol{b.}$ Suppose that the pare of the positive integers $(x_I, y_I)$ is the solution different from founded in $\boldsymbol{a.}\hspace{10mm} x_I^2 - 2 y_I^2 = 1.$ Let $\begin{equation} \left\{ \begin{aligned} x_{i+1} &= 3 x_i - 4 y_i ,\\ y_{i+1} &= - 2 x_i + 3 y_i . \end{aligned} \right.\end{equation}$ then $x_{i+1}^2 - 2 y_{i+1}^2 = (3 x_i - 4 y_i)^2 - 2 (-2 x_i + 3 y_i)^2 = x_i^2 - 2 y_i^2 = 1,$ therefore integers $(x_{i+1}, y_{i+1})$ are the solution of the given equation.

$x_i^2 = 2 y_i^2 +1 > 2 y_i^2 \implies x_i > y_i >0.$ Similarly $x_{i +1}> y_{i+1}.$

There is no integer solution if $y_j = 1. y_j = 0$ is impossible. So $y_i > 1.$ $9 y_i^2 \ge 8 y_i^2 + 4 = 4 x_i^2 \implies 3y_i \ge 2x_i \implies y_{i+1} \ge 0.$

$0 \le y_{i+1} = y_i - 2 (x_i – y_i) < y_i.$

There is no member $y_j = 0$ in the sequence $\{y_i \},$ hence it is infinitely decreasing sequence of natural numbers. There is no such sequence. Contradiction.

vladimir.shelomovskii@gmail.com, vvsss

Equation of the form $x(x + 1) = 2y^2$

Prove that all positive integer solutions of the equation $x(x + 1) = 2y^2$ can be found using recursively transformation $x_{i+1} = 3 x_i + 4 y_i + 1, y_{i+1} = 2 x_i + 3 y_i + 1$ of the pare $\{x_0, y_0\} = \{0,0\}.$ In another form $\sqrt{x_{i+1}} = \sqrt{2x_i} + \sqrt{x_i + 1}.$

Proof

$x(x + 1) = 2y^2 \implies 4x^2 + 4x + 1 = 8y^2 + 1 \implies (2x+1)^2 – 2(2y)^2 = 1.$ It is the form of Pell's equation, therefore $\begin{equation} \left\{ \begin{aligned} 2x_{i+1} + 1 &= 3(2x_i + 1) + 4(2 y_i) ,\\ 2y_{i+1} &= 2(2 x_i + 1) + 3(2 y_i) . \end{aligned} \right. \implies \left\{ \begin{aligned} x_{i+1} &= 3 x_i + 4 y_i + 1 ,\\ y_{i+1} &= 2 x_i + 3 y_i + 1 . \end{aligned} \right. \end{equation}$

$\begin{array}{c|c|c|c|c|c|c|c|c} & & & & & & & & \\ [-2ex] \boldsymbol{i} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ [0.5ex] \hline & & & & & & & & \\ [-1.5ex] \boldsymbol{x_i} & 0 & 1 & 8 & 49 & 288 & 1681 & 9800 & 57121 \\ [1ex] \boldsymbol{y_i} & 0 & 1 & 6 & 35 & 204 & 1189 & 1681 & 40391 \\ [1ex] \end{array}$ $x_{i+1} = 3 x_i + 4 y_i + 1 = 2x_i + 2 \sqrt {2 x_i (x_i + 1)} + (x_i + 1) = (\sqrt {2x_i} + \sqrt{x_i + 1})^2$ $\implies \sqrt{x_{i+1}}= \sqrt{2x_i} + \sqrt{x_i + 1}.$

vladimir.shelomovskii@gmail.com, vvsss

Equation of the form $x^2 – 2y^2 = - 1$

Prove that all positive integer solutions of the equation $x^2 – 2y^2 = -1$ can be found using recursively transformation $x_{i+1} = 3 x_i + 4 y_i , y_{i+1} = 2 x_i + 3 y_i$ of the pare $\{x_0, y_0\} = \{1,1\}.$

Proof Similarly as for equation $x^2 – 2y^2 = 1.$

$\begin{array}{c|c|c|c|c|c|c|c} & & & & & & & \\ [-2ex] \boldsymbol{i} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ [0.5ex] \hline & & & & & & & \\ [-1.5ex] \boldsymbol{x_i} & 1 & 7 & 41 & 239 & 1393 & 8119 & 47321 \\ [1ex] \boldsymbol{y_i} & 1 & 5 & 29 & 169 & 985 & 5741 & 33461 \\ [1ex] \end{array}$

vladimir.shelomovskii@gmail.com, vvsss

Page

Toolbox

Search

Pell's equation (simple solutions)

Equation of the form $x^2 – 2y^2 = 1$

Equation of the form $x(x + 1) = 2y^2$

Equation of the form $x^2 – 2y^2 = - 1$