Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Pell's equation (simple solutions)"

(→‎Equation of the form x^2 – 2y^2 = 1)
(→‎Equation of the form x^2 – 2y^2 = 1)
Line 11: Line 11:
  
 
==Equation of the form <math>x^2 – 2y^2 = 1</math>==
 
==Equation of the form <math>x^2 – 2y^2 = 1</math>==
−
<math>\boldsymbol{a.}</math> Let integers <math>(x_i, y_i)</math> are the solution, <math>\hspace{10mm}  x_i^2 - 2 y_i^2 = 1,</math>
+
Prove that all positive integer solutions of the equation <math>x^2 – 2y^2 = 1</math> can be found using recursively transformation <math>x_{i+1} = 3 x_i + 4 y_i , y_{i+1} = 2 x_i + 3 y_i </math> of the pare <math>\{x_0, y_0\} = \{1,0\}.</math>
 +
 
 +
<i><b>Proof</b></i>
 +
 
 +
<math>\boldsymbol{a.}</math> Let integers <math>(x_i, y_i)</math> are the solution of the equation <math>\hspace{10mm}  x_i^2 - 2 y_i^2 = 1,</math>
 
<cmath>\begin{equation} \left\{ \begin{aligned}  
 
<cmath>\begin{equation} \left\{ \begin{aligned}  
 
   x_{i+1} &= 3 x_i + 4 y_i ,\\
 
   x_{i+1} &= 3 x_i + 4 y_i ,\\
 
   y_{i+1} &= 2 x_i + 3 y_i .
 
   y_{i+1} &= 2 x_i + 3 y_i .
 
\end{aligned} \right.\end{equation}</cmath>
 
\end{aligned} \right.\end{equation}</cmath>
−
then <math>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,</math>
+
Then <cmath>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.</cmath>
 
   
 
   
−
therefore integers <math>(x_{i+1}, y_{i+1})</math> are the solution of the given equation.  
+
Therefore integers <math>(x_{i+1}, y_{i+1})</math> are the solution of the given equation. If <math>i > 0</math> then <cmath>x_{i+1} > y_{i+1}  \ge 2(x_i + y_i) > x_i > y_i > 0.</cmath>
 +
<cmath>\{(x_i, y_i) \} = \{(1,0), (3,2), (17,12), (99,70),...\}.</cmath>
  
−
If <math>i > 0</math> then <math>x_{i+1} > y_{i+1}  \ge 2(x_i + y_i) > 0.</math>
+
<math>\boldsymbol{b.}</math> Suppose that the pare of the positive integers <math>(x_I, y_I)</math> is the solution different from founded in <math>\boldsymbol{a.}\hspace{10mm}  x_I^2 - 2 y_I^2 = 1.</math> Let
−
<cmath>\{(x_i, y_i) \} = \{(1,0), (3,2), (17,12), (99,70),...\}.</cmath>
 
−
<math>\boldsymbol{b.}</math> Let integers <math>(x_i, y_i)</math> are the solution, <math>\hspace{10mm}  x_i^2 - 2 y_i^2 = 1,</math>
 
 
<cmath>\begin{equation} \left\{ \begin{aligned}  
 
<cmath>\begin{equation} \left\{ \begin{aligned}  
 
   x_{i+1} &= 3 x_i - 4 y_i ,\\
 
   x_{i+1} &= 3 x_i - 4 y_i ,\\
Line 30: Line 33:
 
therefore integers <math>(x_{i+1}, y_{i+1})</math> are the solution of the given equation.
 
therefore integers <math>(x_{i+1}, y_{i+1})</math> are the solution of the given equation.
  
−
If <math>x_i > 0, y_i > 0, x_{i+1} > 0, y_{i+1} > 0 </math> then <math>x_{i+1} > y_{i+1}, x_i > y_i .</math>
+
<math>x_i^2 = 2 y_i^2 +1 >  2 y_i^2 \implies  x_i > y_i >0.</math> Similarly <math>x_{i +1}> y_{i+1}.</math>
 +
 
 +
There is no integer solution if <math> y_j = 1. y_j = 0</math> is impossible. So <math>y_i > 1.</math>
 +
<cmath>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.</cmath>
 +
 
 +
<cmath> 0 \le y_{i+1} = y_i - 2 (x_i – y_i) < y_i. </cmath>
 +
 
 +
There is no member <math>y_j  = 0</math> in the sequence <math>\{y_i \},</math> hence it is infinitely decreasing sequence of natural numbers. There is no such sequence. Contradiction.

Revision as of 05:17, 17 April 2023

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Pell%27s_equation_(simple_solutions)&oldid=192256"