LinearRecursion Intermediate

Problem - 2093
If $x$ and $y$ are positive integer solutions to the equation $x^2 - 2y^2 = 1$, then $6\mid xy$.

This is a standard Pell's equation and its fundamental solution is $(x_1, y_1) = (3, 2)$. (See the book %%HREF%%Indeterminate Equation%%http://www.mathallstar.org/Home/Home/35-books/95-book-indeterminate-equations%%.) Therefore all solutions satisfy $$ \left\{ \begin{array}{ll} x_{n+1} & = 3x_n + 4y_n \\ \\ y_{n+1} & = 3y_n + 2 x_n \end{array} \right. $$ When $n=1$, $x_1 y_1 = 3 \times 2 = 6$. The conclusion holds. Assume when $n=k$, this conclusion holds When $n=k+1$, we have $x_{k+1} y_{k+1} = (3x_k +4y_k)(3y_k + 2x_k) = 6x_k^2 +12y_k^2 +27x_ky_k$. Clearly every term on the right is a multiple of 6. Hence the conclusion holds too. Hence, by the principle of induction, the conclusion holds for all the positive integer solutions.

report an error