Proof that x=0 for Integers with Perfect Square Property

[anemone]

The integers $x$ and $y$ have the property that for every non-negative integer $n$, the number $2^nx+y$ is a perfect square.

Show that $x=0$.

 

[Nono713]

This is far from the simplest proof, as it relies on an open (but very likely true, proven conditionally under GRH, etc) conjecture, but I thought it was neat especially since it generalizes to many bases other than $2$. I think it's correct.

Spoiler

Definition: A pair of integers $(x, y)$ is a solution if and only if $2^n x + y$ is a perfect square for all nonnegative integers $n \geq 0$.

Proposition: There are infinitely many (odd) primes $p$ such that $2$ is a primitive root modulo $p$.

Note: This is Artin's conjecture on primitive roots for the case $g = 2$.

Theorem: If $(x, y)$ is a solution and $p > 3$ is an odd prime such that $2$ is a primitive root modulo $p$ then $x$ must be a multiple of $p$.

Proof: Note that there are exactly $1 + (p - 1)/2$ different quadratic residues modulo $p$ (including zero) however the primitive root $2$ generates $p - 1$ different residues modulo $p$, since it generates the group, that is, $\lvert \langle 2 \rangle_p \rvert = p - 1$. Now if $x$ is coprime to $p$ then $\lvert x \langle 2 \rangle_p \rvert = p - 1$ as the multiplication by $x$ modulo $p$ is invertible, and of course $\lvert x \langle 2 \rangle_p + y \rvert = p - 1$ since addition of $y$ modulo $p$ is also invertible for any integer $y$.

Hence if $x$ is coprime to $p$ then $2^n x + y$ assumes $p - 1$ distinct residues modulo $p$ over all $n \geq 0$ whereas perfect squares can only have $1 + (p - 1)/2$ distinct residues modulo $p$, and $1 + (p - 1)/2 < p - 1$ for all $p > 3$, so that $2^n x + y$ cannot be a perfect square for all $n \geq 0$. Thus if $(x, y)$ is a solution then $x$ must be a multiple of $p$. $\blacksquare$

Corollary: If $(x, y)$ is a solution then $x = 0$.

Proof: This follows immediately from the above theorem and proposition which imply that $x$ must be a multiple of infinitely many primes, and the only way this can hold is if $x$ is zero. $\blacksquare$

The argument generalizes for different (non-square) bases other than $2$ by assuming the validity of Artin's conjecture for different primitive roots and some minor modifications. I think you can also adapt it for the case of perfect cubes and such, but I haven't checked. Anyway this is some heavy machinery and I'm sure there's a more elementary proof for this particular challenge.

 

[anemone]

I'm sure there's a more elementary proof for this particular challenge.

Thanks for your well-written solution, Bacterius!

Spoiler

And yes, your intuition is spot on and I would post it (if no one else solved it with elementary method) when this challenge has come close to its "expiration" date.