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 for binomial coefficients)
 
(43 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
During the solution we need:
 
During the solution we need:
  
−
a) to construct a recurrent sequence <math>\{x_{i+1}, y_{i+1} \} = f({x_i, y_i})</math> or two sequences <math>\{x_{i+1} \} = f({x_i}), \{y_{ i+1} \} = g({y_i});</math>
+
a) to construct a recurrent sequence <math>\{x_{i+1}, y_{i+1} \} = f({x_i, y_i});</math>
  
 
b) to prove that the equation has no other integer solutions.
 
b) to prove that the equation has no other integer solutions.
  
−
==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>
−
<cmath>\begin{equation} \left\{ \begin{aligned}  
+
 
−
  x_{i+1} &= 3 x_i + 4 y_i ,\\
+
<i><b>Proof</b></i>
−
  y_{i+1} &= 2 x_i + 3 y_i .
+
 
−
\end{aligned} \right.\end{equation}</cmath>
+
<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>
−
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>
+
 
 +
<cmath>\[ \begin{cases}
 +
x_{i+1} &= 3 x_i + 4 y_i ,\\
 +
y_{i+1} &= 2 x_i + 3 y_i .
 +
  \end{cases} \]</cmath>
 +
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), (577,408), (3363, 2738),...\}.</cmath>
 +
 
 +
<math>\boldsymbol{b.}</math> Suppose that the pare of the positive integers <math>(x_j, y_j)</math> is the solution different from founded in <math>\boldsymbol{a.}</math>
 +
 
 +
<math>x_j^2 - 2 y_j^2 = 1.</math> Let
  
−
If <math>i > 0</math> then <math>x_{i+1} > y_{i+1}  \ge 2(x_i + y_i) > 0.</math>
+
<cmath>\[ \begin{cases}
−
<cmath>\{(x_i, y_i) \} = \{(1,0), (3,2), (17,12), (99,70),...\}.</cmath>
+
x_{i+1} &= 3 x_i - 4 y_i ,\\
−
<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>
+
y_{i+1} &= - 2 x_i + 3 y_i .
−
<cmath>\begin{equation} \left\{ \begin{aligned}  
+
  \end{cases} \]</cmath>
−
  x_{i+1} &= 3 x_i - 4 y_i ,\\
 
−
  y_{i+1} &= - 2 x_i + 3 y_i .
 
−
\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 <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>
 
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.
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form <math>x(x + 1) = 2y^2</math>==
 +
Prove that all positive integer solutions of the equation <math>x(x + 1) = 2y^2</math> can be found using recursively transformation <math>x_{i+1} = 3 x_i + 4 y_i + 1, y_{i+1} = 2 x_i + 3 y_i + 1</math> of the pare <math>\{x_0, y_0\} = \{0,0\}.</math> In another form <math>\sqrt{x_{i+1}} = \sqrt{2x_i} + \sqrt{x_i + 1}.</math>
 +
 
 +
<i><b>Proof</b></i>
 +
 
 +
<cmath>x(x + 1) = 2y^2 \implies 4x^2 + 4x + 1 = 8y^2 + 1 \implies (2x+1)^2 - 2(2y)^2 = 1.</cmath>
 +
It is the form of Pell's equation, therefore
 +
<cmath>\[ \begin{cases}
 +
2x_{i+1}+1 &= 3 (2x_i + 1)+ 4 (2y_i) ,\\
 +
2y_{i+1} &= 2 (2x_i + 1) +3 (2y_i) .
 +
  \end{cases} \]</cmath>
 +
<cmath>\[ \begin{cases}
 +
x_{i+1} &= 3x_i + 4y_i + 1,\\
 +
y_{i+1} &= 2x_i + 3y_i + 1.
 +
  \end{cases} \]</cmath>
 +
 
 +
<cmath>\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}</cmath>
 +
<cmath>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</cmath>
 +
<cmath>\implies \sqrt{x_{i+1}}= \sqrt{2x_i} + \sqrt{x_i + 1}.</cmath>
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form <math>x^2 - 2y^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
 +
<cmath>\[ \begin{cases}
 +
x_{i+1} &= 3 x_i + 4 y_i ,\\
 +
y_{i+1} &= 2 x_i + 3 y_i .
 +
  \end{cases} \]</cmath>
 +
of the pare <math>\{x_0, y_0\} = \{1,1\}.</math>
 +
 
 +
<i><b>Proof</b></i>
 +
 
 +
The solution is similar to that discussed in the previous section.
 +
 
 +
<cmath>\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}</cmath>
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Pythagorean triangles with almost equal legs==
 +
Find all triangles with integer sides one leg of which is <math>1</math> more than the other.
 +
 
 +
Find all natural solutions of the equation <math>x^2 + (x+1)^2 = y^2.</math>
 +
 
 +
<i><b>Solution</b></i>
 +
 
 +
<cmath>x^2 +(x + 1)^2 = 2x^2 + 2x + 1 = y^2 \implies 4x^2 + 4x + 1 = 2y^2 - 1 \implies (2x+1)^2 - 2y^2 = -1.</cmath>
 +
All positive integer solutions of the equation <math>(2x+1)^2 - 2y^2 = -1</math> can be found using recursively transformation
 +
<cmath>\[ \begin{cases}  2x_{i+1}+1 &= 3 (2x_i + 1) + 4 y_i ,\\
 +
y_{i+1} &= 2(2x_i + 1) + 3 y_i .  \end{cases} \]</cmath>
 +
<cmath>\[ \begin{cases} x_{i+1} &= 3x_i + 2y_i + 1 ,\\
 +
y_{i+1} &= 4x_i + 3y_i + 2 . \end{cases} \]</cmath>
 +
of the pare <math>\{x_0, y_0\} = \{0,1\}.</math>
 +
 
 +
<cmath>\begin{array}{c|c|c|c|c|c|c}
 +
& & & & & & \\ [-2ex]
 +
\boldsymbol{i} & 0 & 1 & 2 & 3 & 4 & 5 \\ [0.5ex] \hline 
 +
& & & & & & \\ [-1.5ex]
 +
\boldsymbol{x_i} & 0 & 3 & 20 & 119 & 696 & 4059 \\ [1ex]   
 +
\boldsymbol{y_i} & 1 & 5 & 29 & 169 & 985 & 5741 \\ [1ex]   
 +
\end{array}</cmath>
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form <math>x^2 - 3y^2 = - 1</math>==
 +
Prove that the equation <math>x^2 - 3y^2 = -1</math> have not any solution.
 +
 
 +
<i><b>Proof</b></i>
 +
 
 +
<cmath>x = 3k \implies x^2 \pmod{3}= 0.</cmath>
 +
<cmath>x = 3k \pm 1 \implies x^2 \pmod{3}= 1.</cmath>
 +
<cmath>(- 3y^2 + 1) \pmod {3} = 1 \implies (x^2 - 3y^2 + 1) \pmod {3} = \{1, 2 \} \ne 0 \implies</cmath>
 +
<cmath>x^2 - 3y^2 + 1 \ne 0.</cmath>
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form <math>x^2 - 2y^2 = 7</math>==
 +
Prove that all positive integer solutions of the equation <math>x^2 - 2y^2 = 7</math> can be found using recursively transformation
 +
<cmath>\[ \begin{cases} x_{i+1} &= 3 x_i + 4 y_i ,\\
 +
y_{i+1} &= 2 x_i + 3 y_i . \end{cases} \]</cmath>
 +
of the pares <math>\{x_1, y_1\} = \{3,1\}</math> and <math>\{\hat{x}_1, \hat{y}_1 \} = \{5,3\}</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 = 7,</math>
 +
<cmath>\[ \begin{cases} x_{i+1} &= 3 x_i + 4 y_i ,\\
 +
y_{i+1} &= 2 x_i + 3 y_i . \end{cases} \]</cmath>
 +
 
 +
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 = 7.</cmath>
 +
 +
Therefore integers <math>(x_{i+1}, y_{i+1})</math> are the solution of the given equation.
 +
<cmath>x_{i+1} > y_{i+1}  \ge 2(x_i + y_i) > x_i > y_i > 0.</cmath>
 +
<cmath>\begin{array}{c|c|c|c|c|c}
 +
& & & & & \\ [-2ex]
 +
\boldsymbol{i} & 1 & 2 & 3 & 4 & 5 \\ [0.5ex] \hline 
 +
& & & & & \\ [-1.5ex]
 +
\boldsymbol{x_i} & 3 & 13 & 75 & 437 & 2547 \\ [1ex]   
 +
\boldsymbol{y_i} & 1 & 9 & 53 & 309 & 1801 \\ [1ex]   
 +
\end{array}</cmath>
 +
<math>\boldsymbol{b.}</math> The pare of the positive integers <math>(\hat {x}_i, \hat{y}_i)</math> is the solution different from founded in <math>\boldsymbol{a.}</math>
 +
 
 +
<math>\hat {x}_i^2 - 2 \hat {y}_i^2 = 7.</math> Let
 +
 
 +
<cmath>\[ \begin{cases} \hat{x}_{i+1} &= 3  \hat{x}_i - 4  \hat{y}_i ,\\
 +
\hat{y}_{i+1} &= - 2  \hat{x}_i + 3  \hat{y}_i . \end{cases} \]</cmath>
 +
 
 +
then <cmath>\hat{x}_{i+1}^2 - 2  \hat{y}_{i+1}^2 = (3  \hat{x}_i - 4  \hat{y}_i)^2 - 2 (-2  \hat{x}_i + 3  \hat{y}_i)^2 =  \hat{x}_i^2 - 2  \hat{y}_i^2 = 7,</cmath>
 +
therefore integers <math>( \hat{x}_{i+1},  \hat{y}_{i+1})</math> are the solution of the given equation.
 +
 
 +
<math>\hat{x}_i^2 = 2 \hat{y}_i^2 +1 >  2 \hat{y}_i^2 \implies \hat{x}_i > \hat{y}_i > 0.</math> Similarly <math>\hat{x}_{i +1} > \hat{y}_{i+1}.</math>
 +
 
 +
If <math> \hat{y}_i > 5</math> then
 +
<cmath>9 \hat{y}_i^2 \ge 8 \hat{y}_i^2 + 28  = 4 \hat{x}_i^2 \implies 3 \hat{y}_i \ge 2 \hat{x}_i  \implies \hat{y}_{i+1} \ge 0.</cmath>
 +
 
 +
<cmath> 0 \le \hat{y}_{i+1} = \hat{y}_i - 2 (\hat{x}_i – \hat{y}_i) <\hat{y}_i. </cmath>
 +
 
 +
There is no member <math>\hat{y}_j  = 0</math> in the sequence <math>\{\hat{y}_i \},</math> hence it is infinitely decreasing sequence of natural numbers. There is no such sequence. Contradiction.
 +
 
 +
We need to check <math>\hat{y}_j = \{2,4,5\}</math> (no solution), but <math>\hat{y}_j = 3</math> gives the integer solution, so there is the second sequence of the integer solutions
 +
<cmath>\begin{array}{c|c|c|c|c|c}
 +
& & & & & \\ [-2ex]
 +
\boldsymbol{i} & 1 & 2 & 3 & 4 & 5 \\ [0.5ex] \hline 
 +
& & & & & \\ [-1.5ex]
 +
\boldsymbol{\hat{x}_i} & 5 & 27 & 157 & 915 & 5333 \\ [1ex]   
 +
\boldsymbol{\hat{y}_i} & 3 & 19 & 111 & 647 & 3771 \\ [1ex]   
 +
\end{array}</cmath>
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form <math>x^2 - xy - y^2 = 1</math>==
 +
Prove that all positive integer solutions of the equation <math>x^2 - xy - y^2 = 1</math> are <math>\{x_i, y_i \} = \{F_{2i +1}, F_{2i}\}.</math> They can be found using recursively transformation <math>y_{i+1} = x_i + y_i , x_{i+1} = 2x_i + y_i = y_{i+1} + x_i </math> of the pares <math>\{x_0, y_0\} = \{1,0\}.</math>
 +
 
 +
<i><b>Proof</b></i>
 +
<cmath>x^2 - xy - y^2 = 1 \implies 4x^2 - 4xy + y^2 - 5y^2 = 1 \implies (2x+y)^2 - 5y^2 = 1.</cmath>
 +
Let the pare of the positive integers <math>(x_i, y_i)</math> be the solution of given equation <math> x_i^2 - x_i y_i - y_i^2 = 1</math> and 
 +
<cmath>\[ \begin{cases} x_{i+1} &= 2x_i + y_i ,\\
 +
y_{i+1} &= x_i + y_i .  \end{cases} \]</cmath>
 +
Then
 +
<cmath>x_{i + 1}^2 - x_{i + 1} y_{i + 1} - y_{i + 1}^2 = x_i^2 - x_i y_i - y_i^2 = 1.</cmath>
 +
<cmath>\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} & 1 & 2 & 5 & 13 & 34 & 89 & 233 & 610 \\ [1ex]   
 +
\boldsymbol{y_i} & 0 & 1 & 3 & 8 & 21 & 55 & 144 & 377 \\ [1ex]   
 +
\end{array}</cmath>
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form <math>x^2 - xy - y^2 = -1</math>==
 +
Prove that all positive integer solutions of the equation <math>x^2 - xy - y^2 = -1</math> are <math>\{x_i, y_i \} = \{F_{2i}, F_{2i-1}\}.</math> They can be found using recursively transformation
 +
<cmath>\[ \begin{cases} x_{i+1} &= 2x_i + y_i = y_{i+1} + x_i,\\
 +
y_{i+1} &= x_i + y_i .  \end{cases} \]</cmath>
 +
of the pares <math>\{x_0, y_0\} = \{1,1\} = \{F_1, F_2 \}.</math>
 +
<cmath>\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} & 1 & 3 & 8 & 21 & 55 & 144 & 377 & 987 \\ [1ex]   
 +
\boldsymbol{y_i} & 1 & 2 & 5 & 13 & 34 & 89 & 233 & 610 \\ [1ex]   
 +
\end{array}</cmath>
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form <math>x^2 - 5y^2 = 4</math>==
 +
Prove that all positive integer solutions of the equation <math>x^2 - 5y^2 = 4</math> are <cmath>\{x_i, y_i \} = \{F_{2i+1} + F_{2i - 1}, F_{2i}\}.</cmath>
 +
It is clear that solutions can be found using recursively transformation
 +
<cmath>\[ \begin{cases} x_{i+1} = \frac {3x_i }{2}+ \frac {5y_i }{2},\\
 +
y_{i+1} = \frac {x_i }{2}+ \frac {3y_i }{2}  \end{cases} \]</cmath>
 +
of the pare <math>\{x_1, y_1\} = \{3, 1\} = \{F_3 +F_1, F_2\}.</math>
 +
 +
One can use the small transform for understanding
 +
<cmath>x_{i + 1} - y_{i + 1} = x_i + y_i = (x_i - y_i) + 2y_i  \Rightarrow 2F_{2i+1} = 2F_{2i-1} + 2F_{2i}, x_1-y_1 = 2F_1.</cmath>
 +
<cmath>y_{i + 1} = \frac {x_i - y_i}{2}+ 2 y_i  \Rightarrow    F_{2i +2} = F_{2i-1} + 2F_{2i} =  F_{2i+1} + F_{2i}, y_1 = F_2.</cmath>
 +
<cmath>\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} & 3 & 7 & 18 & 47 & 123 & 322 & 377 & 843 \\ [1ex]   
 +
\boldsymbol{y_i} & 1 & 3 & 8 & 21 & 55 & 89 & 144 & 377 \\ [1ex]   
 +
\end{array}</cmath>
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation for binomial coefficients==
 +
Find all positive integer solutions of equation  <math>\binom{x}{y-1} = \binom{x-1}{y}.</math>
 +
 
 +
<i><b>Solution</b></i>
 +
<cmath>\binom{x}{y-1} = \frac{x!}{(y-1)!(x-y+1)!}, \binom{x-1}{y} = \frac{(x-1)!}{y!(x-y-1)!} \implies </cmath>
 +
<cmath>xy=(x-y+1) \cdot (x-y) \implies x^2 -3xy +y^2 +x - y = 0.</cmath>
 +
It is known that every real quadratic form under a linear change of variables may be transformed in a "diagonal form".
 +
<cmath>(x + \frac {1}{5})^2 + (y - \frac {1}{5})^2 - 3 (x + \frac {1}{5})(y - \frac {1}{5}) = \frac {1}{5},</cmath>
 +
<cmath>(5y - 1)^2 - 5 (2x - 3y + 1)^2 = - 4,</cmath>
 +
<cmath>u = 5y - 1, v = 2x - 3y + 1 \implies u^2 - 5 v^2 = - 4 \implies</cmath>
 +
 
 +
<cmath>\[ \begin{cases} u_i = 5y_i - 1 = F_{2i} + F_{2i - 2},\\
 +
v_i = 2x_i - 3y_i + 1 = F_{2i-1}. \end{cases} \]</cmath>
 +
<cmath>y_i = \frac {F_{2i} + F_{2i - 2} + 1}{5} = \frac {L_{2i - 1} + 1}{5},</cmath> where L is Lucas number,
 +
<math>L_0 = 2, L_1 = 1, L_i = F_{i-1} + F_{i+1} = L_i + L_{i - 1}.</math>
 +
It is clear that <cmath>\{L_i \} = \{2,1,3,4,\hspace{5mm}  7,11,18,29, \hspace{5mm}  47,...\}</cmath>
 +
<cmath>\{L_i \pmod 5 \} = \{2,1,3,4, \hspace{5mm} 2,1,3,4,\hspace{5mm} 2,...\}</cmath>
 +
<cmath>L_i \pmod 5 = (L_{i-1} \pmod 5 + L_{i-2} \pmod 5 ) \pmod 5 = L_{i+4} \pmod 5,</cmath>
 +
so sequence of Lucas numbers modulo <math>5</math> is periodic, the period is <math>4,</math> and the numbers with index <math>4i-1</math> (only these numbers) are <math>4</math> modulo <math>5.</math>
 +
 
 +
Therefore only numbers <cmath>y_i = \frac {F_{4i} + F_{4i – 2} + 1}{5}</cmath> are integer.
 +
 
 +
We use the identities <cmath>F_{2i-1}^2- F_{2i} \cdot F_{2i-2} = 1, F_{4i} = F_{2i} (F_{2i+1} + F_{2i-1}),
 +
F_{4i – 2} = F_{2i-1}(2F_{2i} - F_{2i-1})</cmath> and get  <cmath>y_i = F_{2i} F_{2i-1}.</cmath>
 +
 
 +
We use the identities <cmath>F_{4i-1}= F_{2i}^2 + F_{2i-1}^2, F_{2i-1}^2 - F_{2i} \cdot F_{2i-2} = 1,</cmath>
 +
and get
 +
<cmath>x_i = \frac{ 3y_i - 1 + F_{4i-1}}{2} =  \frac{ F_{2i}(3F_{2i-1} + F_{2i} +F_{2i-2})}{2} =  F_{2i} \cdot F_{2i+1}.</cmath>
 +
 
 +
<cmath>\begin{array}{c|c|c|c|c|c|c|c}
 +
& & & & & & & \\ [-2ex]
 +
\boldsymbol{i} & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ [0.5ex] \hline 
 +
& & & & & & & \\ [-1.5ex]
 +
\boldsymbol{u_i} & 1 & 4 & 11 & 29 & 76 & 199 & 521  \\ [1ex]   
 +
\boldsymbol{v_i} & 1 & 2 & 5 & 13 & 34 & 89 & 233 \\ [1ex]   
 +
\boldsymbol{x_i} & 2 & 15 & 104 & 714 & 4895 & 33552 & 229970 \\ [1ex]   
 +
\boldsymbol{y_i} & 1 & 6 & 40 & 273 & 1870 & 12816 & 87841 \\ [1ex]   
 +
\end{array}</cmath>
 +
<cmath>\binom{15}{5} = \binom{14}{6} =  3003</cmath>
 +
<cmath>\binom{104}{39} = \binom{103}{40} =  61218182743304701891431482520</cmath>
 +
 
 +
'''vladimir.shelomovskii@gmail.com, vvsss'''
 +
 
 +
==Equation of the form==

Latest revision as of 07:28, 20 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});$

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{cases} x_{i+1} &= 3 x_i + 4 y_i ,\\ y_{i+1} &= 2 x_i + 3 y_i . \end{cases} \] 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), (577,408), (3363, 2738),...\}.\]

$\boldsymbol{b.}$ Suppose that the pare of the positive integers $(x_j, y_j)$ is the solution different from founded in $\boldsymbol{a.}$

$x_j^2 - 2 y_j^2 = 1.$ Let

\[ \begin{cases} x_{i+1} &= 3 x_i - 4 y_i ,\\ y_{i+1} &= - 2 x_i + 3 y_i . \end{cases} \] 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{cases} 2x_{i+1}+1 &= 3 (2x_i + 1)+ 4 (2y_i) ,\\ 2y_{i+1} &= 2 (2x_i + 1) +3 (2y_i) . \end{cases} \] \[ \begin{cases} x_{i+1} &= 3x_i + 4y_i + 1,\\ y_{i+1} &= 2x_i + 3y_i + 1. \end{cases} \]

\[\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 \[ \begin{cases} x_{i+1} &= 3 x_i + 4 y_i ,\\ y_{i+1} &= 2 x_i + 3 y_i . \end{cases} \] of the pare $\{x_0, y_0\} = \{1,1\}.$

Proof

The solution is similar to that discussed in the previous section.

\[\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

Pythagorean triangles with almost equal legs

Find all triangles with integer sides one leg of which is $1$ more than the other.

Find all natural solutions of the equation $x^2 + (x+1)^2 = y^2.$

Solution

\[x^2 +(x + 1)^2 = 2x^2 + 2x + 1 = y^2 \implies 4x^2 + 4x + 1 = 2y^2 - 1 \implies (2x+1)^2 - 2y^2 = -1.\] All positive integer solutions of the equation $(2x+1)^2 - 2y^2 = -1$ can be found using recursively transformation \[ \begin{cases} 2x_{i+1}+1 &= 3 (2x_i + 1) + 4 y_i ,\\ y_{i+1} &= 2(2x_i + 1) + 3 y_i . \end{cases} \] \[ \begin{cases} x_{i+1} &= 3x_i + 2y_i + 1 ,\\ y_{i+1} &= 4x_i + 3y_i + 2 . \end{cases} \] of the pare $\{x_0, y_0\} = \{0,1\}.$

\[\begin{array}{c|c|c|c|c|c|c} & & & & & & \\ [-2ex] \boldsymbol{i} & 0 & 1 & 2 & 3 & 4 & 5 \\ [0.5ex] \hline & & & & & & \\ [-1.5ex] \boldsymbol{x_i} & 0 & 3 & 20 & 119 & 696 & 4059 \\ [1ex] \boldsymbol{y_i} & 1 & 5 & 29 & 169 & 985 & 5741 \\ [1ex] \end{array}\]

vladimir.shelomovskii@gmail.com, vvsss

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

Prove that the equation $x^2 - 3y^2 = -1$ have not any solution.

Proof

\[x = 3k \implies x^2 \pmod{3}= 0.\] \[x = 3k \pm 1 \implies x^2 \pmod{3}= 1.\] \[(- 3y^2 + 1) \pmod {3} = 1 \implies (x^2 - 3y^2 + 1) \pmod {3} = \{1, 2 \} \ne 0 \implies\] \[x^2 - 3y^2 + 1 \ne 0.\] vladimir.shelomovskii@gmail.com, vvsss

Equation of the form $x^2 - 2y^2 = 7$

Prove that all positive integer solutions of the equation $x^2 - 2y^2 = 7$ can be found using recursively transformation \[ \begin{cases} x_{i+1} &= 3 x_i + 4 y_i ,\\ y_{i+1} &= 2 x_i + 3 y_i . \end{cases} \] of the pares $\{x_1, y_1\} = \{3,1\}$ and $\{\hat{x}_1, \hat{y}_1 \} = \{5,3\}$.

Proof

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

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 = 7.\]

Therefore integers $(x_{i+1}, y_{i+1})$ are the solution of the given equation. \[x_{i+1} > y_{i+1} \ge 2(x_i + y_i) > x_i > y_i > 0.\] \[\begin{array}{c|c|c|c|c|c} & & & & & \\ [-2ex] \boldsymbol{i} & 1 & 2 & 3 & 4 & 5 \\ [0.5ex] \hline & & & & & \\ [-1.5ex] \boldsymbol{x_i} & 3 & 13 & 75 & 437 & 2547 \\ [1ex] \boldsymbol{y_i} & 1 & 9 & 53 & 309 & 1801 \\ [1ex] \end{array}\] $\boldsymbol{b.}$ The pare of the positive integers $(\hat {x}_i, \hat{y}_i)$ is the solution different from founded in $\boldsymbol{a.}$

$\hat {x}_i^2 - 2 \hat {y}_i^2 = 7.$ Let

\[ \begin{cases} \hat{x}_{i+1} &= 3 \hat{x}_i - 4 \hat{y}_i ,\\ \hat{y}_{i+1} &= - 2 \hat{x}_i + 3 \hat{y}_i . \end{cases} \]

then \[\hat{x}_{i+1}^2 - 2 \hat{y}_{i+1}^2 = (3 \hat{x}_i - 4 \hat{y}_i)^2 - 2 (-2 \hat{x}_i + 3 \hat{y}_i)^2 = \hat{x}_i^2 - 2 \hat{y}_i^2 = 7,\] therefore integers $( \hat{x}_{i+1}, \hat{y}_{i+1})$ are the solution of the given equation.

$\hat{x}_i^2 = 2 \hat{y}_i^2 +1 > 2 \hat{y}_i^2 \implies \hat{x}_i > \hat{y}_i > 0.$ Similarly $\hat{x}_{i +1} > \hat{y}_{i+1}.$

If $\hat{y}_i > 5$ then \[9 \hat{y}_i^2 \ge 8 \hat{y}_i^2 + 28 = 4 \hat{x}_i^2 \implies 3 \hat{y}_i \ge 2 \hat{x}_i \implies \hat{y}_{i+1} \ge 0.\]

\[0 \le \hat{y}_{i+1} = \hat{y}_i - 2 (\hat{x}_i – \hat{y}_i) <\hat{y}_i.\]

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

We need to check $\hat{y}_j = \{2,4,5\}$ (no solution), but $\hat{y}_j = 3$ gives the integer solution, so there is the second sequence of the integer solutions \[\begin{array}{c|c|c|c|c|c} & & & & & \\ [-2ex] \boldsymbol{i} & 1 & 2 & 3 & 4 & 5 \\ [0.5ex] \hline & & & & & \\ [-1.5ex] \boldsymbol{\hat{x}_i} & 5 & 27 & 157 & 915 & 5333 \\ [1ex] \boldsymbol{\hat{y}_i} & 3 & 19 & 111 & 647 & 3771 \\ [1ex] \end{array}\] vladimir.shelomovskii@gmail.com, vvsss

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

Prove that all positive integer solutions of the equation $x^2 - xy - y^2 = 1$ are $\{x_i, y_i \} = \{F_{2i +1}, F_{2i}\}.$ They can be found using recursively transformation $y_{i+1} = x_i + y_i , x_{i+1} = 2x_i + y_i = y_{i+1} + x_i$ of the pares $\{x_0, y_0\} = \{1,0\}.$

Proof \[x^2 - xy - y^2 = 1 \implies 4x^2 - 4xy + y^2 - 5y^2 = 1 \implies (2x+y)^2 - 5y^2 = 1.\] Let the pare of the positive integers $(x_i, y_i)$ be the solution of given equation $x_i^2 - x_i y_i - y_i^2 = 1$ and \[ \begin{cases} x_{i+1} &= 2x_i + y_i ,\\ y_{i+1} &= x_i + y_i . \end{cases} \] Then \[x_{i + 1}^2 - x_{i + 1} y_{i + 1} - y_{i + 1}^2 = x_i^2 - x_i y_i - y_i^2 = 1.\] \[\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} & 1 & 2 & 5 & 13 & 34 & 89 & 233 & 610 \\ [1ex] \boldsymbol{y_i} & 0 & 1 & 3 & 8 & 21 & 55 & 144 & 377 \\ [1ex] \end{array}\]

vladimir.shelomovskii@gmail.com, vvsss

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

Prove that all positive integer solutions of the equation $x^2 - xy - y^2 = -1$ are $\{x_i, y_i \} = \{F_{2i}, F_{2i-1}\}.$ They can be found using recursively transformation \[ \begin{cases} x_{i+1} &= 2x_i + y_i = y_{i+1} + x_i,\\ y_{i+1} &= x_i + y_i . \end{cases} \] of the pares $\{x_0, y_0\} = \{1,1\} = \{F_1, F_2 \}.$ \[\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} & 1 & 3 & 8 & 21 & 55 & 144 & 377 & 987 \\ [1ex] \boldsymbol{y_i} & 1 & 2 & 5 & 13 & 34 & 89 & 233 & 610 \\ [1ex] \end{array}\]

vladimir.shelomovskii@gmail.com, vvsss

Equation of the form $x^2 - 5y^2 = 4$

Prove that all positive integer solutions of the equation $x^2 - 5y^2 = 4$ are \[\{x_i, y_i \} = \{F_{2i+1} + F_{2i - 1}, F_{2i}\}.\] It is clear that solutions can be found using recursively transformation \[ \begin{cases} x_{i+1} = \frac {3x_i }{2}+ \frac {5y_i }{2},\\ y_{i+1} = \frac {x_i }{2}+ \frac {3y_i }{2} \end{cases} \] of the pare $\{x_1, y_1\} = \{3, 1\} = \{F_3 +F_1, F_2\}.$

One can use the small transform for understanding \[x_{i + 1} - y_{i + 1} = x_i + y_i = (x_i - y_i) + 2y_i \Rightarrow 2F_{2i+1} = 2F_{2i-1} + 2F_{2i}, x_1-y_1 = 2F_1.\] \[y_{i + 1} = \frac {x_i - y_i}{2}+ 2 y_i \Rightarrow F_{2i +2} = F_{2i-1} + 2F_{2i} = F_{2i+1} + F_{2i}, y_1 = F_2.\] \[\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} & 3 & 7 & 18 & 47 & 123 & 322 & 377 & 843 \\ [1ex] \boldsymbol{y_i} & 1 & 3 & 8 & 21 & 55 & 89 & 144 & 377 \\ [1ex] \end{array}\]

vladimir.shelomovskii@gmail.com, vvsss

Equation for binomial coefficients

Find all positive integer solutions of equation $\binom{x}{y-1} = \binom{x-1}{y}.$

Solution \[\binom{x}{y-1} = \frac{x!}{(y-1)!(x-y+1)!}, \binom{x-1}{y} = \frac{(x-1)!}{y!(x-y-1)!} \implies\] \[xy=(x-y+1) \cdot (x-y) \implies x^2 -3xy +y^2 +x - y = 0.\] It is known that every real quadratic form under a linear change of variables may be transformed in a "diagonal form". \[(x + \frac {1}{5})^2 + (y - \frac {1}{5})^2 - 3 (x + \frac {1}{5})(y - \frac {1}{5}) = \frac {1}{5},\] \[(5y - 1)^2 - 5 (2x - 3y + 1)^2 = - 4,\] \[u = 5y - 1, v = 2x - 3y + 1 \implies u^2 - 5 v^2 = - 4 \implies\]

\[ \begin{cases} u_i = 5y_i - 1 = F_{2i} + F_{2i - 2},\\ v_i = 2x_i - 3y_i + 1 = F_{2i-1}. \end{cases} \] \[y_i = \frac {F_{2i} + F_{2i - 2} + 1}{5} = \frac {L_{2i - 1} + 1}{5},\] where L is Lucas number, $L_0 = 2, L_1 = 1, L_i = F_{i-1} + F_{i+1} = L_i + L_{i - 1}.$ It is clear that \[\{L_i \} = \{2,1,3,4,\hspace{5mm} 7,11,18,29, \hspace{5mm} 47,...\}\] \[\{L_i \pmod 5 \} = \{2,1,3,4, \hspace{5mm} 2,1,3,4,\hspace{5mm} 2,...\}\] \[L_i \pmod 5 = (L_{i-1} \pmod 5 + L_{i-2} \pmod 5 ) \pmod 5 = L_{i+4} \pmod 5,\] so sequence of Lucas numbers modulo $5$ is periodic, the period is $4,$ and the numbers with index $4i-1$ (only these numbers) are $4$ modulo $5.$

Therefore only numbers \[y_i = \frac {F_{4i} + F_{4i – 2} + 1}{5}\] are integer.

We use the identities \[F_{2i-1}^2- F_{2i} \cdot F_{2i-2} = 1, F_{4i} = F_{2i} (F_{2i+1} + F_{2i-1}), F_{4i – 2} = F_{2i-1}(2F_{2i} - F_{2i-1})\] and get \[y_i = F_{2i} F_{2i-1}.\]

We use the identities \[F_{4i-1}= F_{2i}^2 + F_{2i-1}^2, F_{2i-1}^2 - F_{2i} \cdot F_{2i-2} = 1,\] and get \[x_i = \frac{ 3y_i - 1 + F_{4i-1}}{2} = \frac{ F_{2i}(3F_{2i-1} + F_{2i} +F_{2i-2})}{2} = F_{2i} \cdot F_{2i+1}.\]

\[\begin{array}{c|c|c|c|c|c|c|c} & & & & & & & \\ [-2ex] \boldsymbol{i} & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ [0.5ex] \hline & & & & & & & \\ [-1.5ex] \boldsymbol{u_i} & 1 & 4 & 11 & 29 & 76 & 199 & 521 \\ [1ex] \boldsymbol{v_i} & 1 & 2 & 5 & 13 & 34 & 89 & 233 \\ [1ex] \boldsymbol{x_i} & 2 & 15 & 104 & 714 & 4895 & 33552 & 229970 \\ [1ex] \boldsymbol{y_i} & 1 & 6 & 40 & 273 & 1870 & 12816 & 87841 \\ [1ex] \end{array}\] \[\binom{15}{5} = \binom{14}{6} = 3003\] \[\binom{104}{39} = \binom{103}{40} = 61218182743304701891431482520\]

vladimir.shelomovskii@gmail.com, vvsss

Equation of the form

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