Prove that for each positive integer $n$ there exist odd positive integers $x_n$ and $y_n$ such that ${x_{n}}^2 +7{y_{n}}^2 =2^n$.
Problem
Source:
Tags: modular arithmetic, Diophantine Equations
30.08.2007 15:48
The exact result is false, since $ n\ge3$ is required. Define $ x_{3}= y_{3}= 1$, and define recursively \[ (x_{n+1},y_{n+1})=\{\begin{array}{ll}(\frac{|7x_{n}-y_{n}|}{2},\frac{x_{n}+y_{n}}{2}) &\text{ if }x_{n}\equiv y_{n}\pmod4,\\ (\frac{7x_{n}+y_{n}}{2},\frac{|x_{n}-y_{n}|}{2}) &\text{ if }x_{n}\not\equiv y_{n}\pmod 4.\end{array}\] Then obviously $ x_{n+1}^{2}+7y_{n+1}^{2}= 2^{n+1}$, and both are odd, so we have constructed such integers. [solution neatly rewritten from here]
21.12.2011 10:26
It is a problem from Bulgarian MO 1996 - Regional Round. http://imomath.com/othercomp/Bul/BulMO396.pdf You can find a solution on the Bulgarian MO offical site - http://www.math.bas.bg/bcmi/ too.
08.01.2016 08:08
Let $(x, y) = x^2 + 7y^2$ and define the composition rule $(x_1, y_1) \cdot (x_2, y_2) = (x_1x_2 - 7y_1y_2, x_1y_2 + x_2y_1)$ (corresponding to the identity $(x_1^2 + 7y_1^2)(x_2^2 + 7y_2^2) = (x_1x_2 - 7y_1y_2)^2 + 7(x_1y_2 + x_2y_1)^2$). Since both $x_1x_2 - 7y_1y_2$ and $x_1y_2 + x_2y_1$ are even (given that we are composing odd solutions), we want $x_1x_2 - 7y_1y_2 \equiv_4 2$ and $x_1y_2 + x_2y_1 \equiv_4 2$. We can obtain odd solutions for $n+1$ (which Peter listed above) by carrying out the composition $(x_n, y_n) \cdot (1, 1)$ if $x_n \equiv_4 y_n$ and $(x_n, y_n) \cdot (-1, 1)$ if $x_n \not\equiv_4 y_n$.