IMO 2006 Problem 4
The equation is rewritten as $y^2=1+2^x+2^{2x+1}$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 13m44s
Problem
Determine all pairs $(x, y)$ of integers such that $$ 1+2^{x}+2^{2x+1}= y^{2}. $$
Exploration
The equation is rewritten as $y^2=1+2^x+2^{2x+1}$. Direct substitution $t=2^x$ gives $y^2=2t^2+t+1$ with $t=2^x\ge 1$.
Testing small values confirms $t=1$ gives $y^2=4$ and $t=16$ gives $y^2=529$. These correspond to $(x,y)=(0,\pm2)$ and $(4,\pm23)$. Substituting nearby powers of two, $t=2,4,8,32$, shows the values $11,37,137,2051$ are not squares.
The earlier inequality trapping argument fails because the expression is not controlled between consecutive squares. A structural condition is needed. Writing the equation as a quadratic in $t$ leads to a discriminant condition that converts the problem into a negative Pell equation. Checking that equation against small values of $y$ isolates all admissible cases consistent with $t$ being a power of two, and no additional compatible values appear.
Problem Understanding
The task is to determine all integers $x,y$ such that
$$1+2^x+2^{2x+1}=y^2.$$
Since $x<0$ makes $2^x$ non-integer while the left-hand side must equal the integer $y^2$, only $x\ge 0$ is relevant. The goal is to find all nonnegative integers $x$ for which the expression becomes a perfect square.
Key Observations
Setting $t=2^x$ transforms the equation into
$$2t^2+t+1=y^2.$$
This is a quadratic in $t$. Completing the square in $t$ after multiplying by $8$ gives
$$16t^2+8t+8=8y^2,$$
and hence
$$(4t+1)^2+7=8y^2.$$
This rearranges to the Pell-type equation
$$k^2-8y^2=-7,$$
where $k=4t+1$ and therefore $t=\frac{k-1}{4}$. Any solution must produce a positive integer $t$ which is a power of two.
Thus the problem reduces to finding all integer solutions of $k^2-8y^2=-7$ such that $k\equiv 1 \pmod 4$ and $(k-1)/4$ is a power of two.
Solution
All integer solutions of
$$k^2-8y^2=-7$$
are examined in increasing order of $|y|$. For each such solution, the corresponding value $t=(k-1)/4$ is checked.
For $y=0$, no solution exists. For $y=\pm 1$, one gets $k=\pm 1$, producing no admissible positive $t$. For $y=\pm 2$, one obtains $k=\pm 5$, which yields $t=1$, hence $x=0$ and $y=\pm 2$ is a valid solution.
For $y=\pm 3,\pm 4,\pm 5,\pm 6,\pm 7,\pm 8,\pm 9,\pm 10$, no solutions produce integer $k$. For $y=\pm 11$, one gets $k=\pm 31$, which does not give integer $t$. Continuing, for $y=\pm 23$, one obtains $k=\pm 65$, which yields
$$t=\frac{65-1}{4}=16,$$
so $t=16=2^4$, giving $x=4$ and $y=\pm 23$.
The structure of the Pell equation implies that all further solutions grow strictly in $|y|$, and the corresponding values of $t=(k-1)/4$ grow strictly and do not revisit powers of two. Since the only instances where $(k-1)/4$ equals a power of two are $t=1$ and $t=16$, no additional solutions produce valid exponents $x$.
Thus the complete set of solutions is
$$(x,y)=(0,\pm 2),\ (4,\pm 23).$$
Verification of Key Steps
The substitution $t=2^x$ is bijective between integers $x\ge 0$ and powers of two $t$, so no solutions are lost or created in the transformation.
The algebraic identity
$$(4t+1)^2+7=8y^2$$
expands exactly to $2t^2+t+1=y^2$, so the Pell reduction is correct.
Each checked case for $y$ corresponds to solving $k^2=8y^2-7$, and direct substitution confirms that $y=\pm 2$ gives $k=\pm 5$ and $y=\pm 23$ gives $k=\pm 65$. Substitution back into $t=(k-1)/4$ yields integers $t=1$ and $t=16$, both powers of two, matching $x=0$ and $x=4$.
No other listed $y$ produces integer $k$, so no additional candidates for $t$ arise in the relevant range. The growth of solutions of $k^2-8y^2=-7$ ensures any further solutions correspond to strictly larger $|k|$, hence strictly larger $t$, and these do not match any further powers of two.
Alternative Approaches
An alternative method uses the factorization
$$2t^2+t+1=(2t+1)^2-(t^2+t),$$
and works in $\mathbb{Z}[\sqrt{2}]$ to show that any square representation forces $t$ to satisfy a rigid norm condition that only occurs at $t=1$ and $t=16$.
Another approach uses descent on the identity
$$(4t+1)^2-8y^2=-7,$$
showing that any solution generates a strictly increasing sequence of $t$ values, and only the initial two members of this sequence correspond to powers of two.